Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-34244
Titel: | Variety Membership Testing in Algebraic Complexity Theory |
VerfasserIn: | Pandey, Anurag |
Sprache: | Englisch |
Erscheinungsjahr: | 2021 |
Freie Schlagwörter: | 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-Sachgruppe: | 510 Mathematik |
Dokumenttyp: | 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 zu diesem Datensatz: | urn:nbn:de:bsz:291--ds-342440 hdl:20.500.11880/31479 http://dx.doi.org/10.22028/D291-34244 |
Erstgutachter: | Bläser, Markus |
Tag der mündlichen Prüfung: | 17-Jun-2021 |
Datum des Eintrags: | 6-Jul-2021 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Professur: | MI - Prof. Dr. Markus Bläser |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
thesis_pandey_anurag.pdf | 1,05 MB | Adobe PDF | Öffnen/Anzeigen |
Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons