Please use this identifier to cite or link to this item: doi:10.22028/D291-34244
Title: Variety Membership Testing in Algebraic Complexity Theory
Author(s): Pandey, Anurag
Language: English
Year of Publication: 2021
Free key words: Complexity Theory
Algebraic Complexity Theory
Variety Membership Testing
Slice Rank
Tensor Rank
Orbit Closure
Polynomial Identity Testing
Matrix Rank
Symbolic matrices
Randomized algorithms
Approximation Algorithms
Geometric Complexity Theory
Algebraic Branching Programs
P versus NP
DDC notations: 510 Mathematics
Publikation type: Dissertation
Abstract: In this thesis, we study some of the central problems in algebraic complexity theory through the lens of the variety membership testing problem. In the first part, we investigate whether separations between algebraic complexity classes can be phrased as instances of the variety membership testing problem. For this, we compare some complexity classes with their closures. We show that monotone commutative single-(source, sink) ABPs are closed. Further, we prove that multi-(source, sink) ABPs are not closed in both the monotone commutative and the noncommutative settings. However, the corresponding complexity classes are closed in all these settings. Next, we observe a separation between the complexity class VQP and the closure of VNP. In the second part, we cover the blackbox polynomial identity testing (PIT) problem, and the rank computation problem of symbolic matrices, both phrasable as instances of the variety membership testing problem. For the blackbox PIT, we give a randomized polynomial time algorithm that uses the number of random bits that matches the information-theoretic lower bound, differing from it only in the lower order terms. For the rank computation problem, we give a deterministic polynomial time approximation scheme (PTAS) when the degrees of the entries of the matrices are bounded by a constant. Finally, we show NP-hardness of two problems on 3-tensors, both of which are instances of the variety membership testing problem. The first problem is the orbit closure containment problem for the action of GLk x GLm x GLn on 3-tensors, while the second problem is to decide whether the slice rank of a given 3-tensor is at most r.
Link to this record: urn:nbn:de:bsz:291--ds-342440
Advisor: Bläser, Markus
Date of oral examination: 17-Jun-2021
Date of registration: 6-Jul-2021
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Professorship: MI - Prof. Dr. Markus Bläser
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
thesis_pandey_anurag.pdf1,05 MBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons