Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory

Bläser, M., Ikenmeyer, C., Lysikov, V., Pandey, A., & Schreyer, F.-O. (2019). Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory. Retrieved from http://arxiv.org/abs/1911.02534.

Item is

Basisdaten

einblenden: ausblenden:
Genre: Forschungspapier

Dateien

einblenden: Dateien
ausblenden: Dateien
:
arXiv:1911.02534.pdf (Preprint), 613KB
Name:
arXiv:1911.02534.pdf
Beschreibung:
File downloaded from arXiv at 2019-11-15 10:59
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Bläser, Markus1, Autor
Ikenmeyer, Christian1, Autor           
Lysikov, Vladimir1, Autor
Pandey, Anurag2, Autor           
Schreyer, Frank-Olaf1, Autor
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Computer Science, Computational Complexity, cs.CC,Mathematics, Algebraic Geometry, math.AG,Mathematics, Representation Theory, math.RT
 Zusammenfassung: We study the variety membership testing problem in the case when the variety
is given as an orbit closure and the ambient space is the set of all 3-tensors.
The first variety that we consider is the slice rank variety, which consists of
all 3-tensors of slice rank at most $r$. We show that the membership testing
problem for the slice rank variety is $\NP$-hard. While the slice rank variety
is a union of orbit closures, we define another variety, the minrank variety,
expressible as a single orbit closure. Our next result is the $\NP$-hardness of
membership testing in the minrank variety, hence we establish the
$\NP$-hardness of the orbit closure containment problem for 3-tensors.
Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk
and independently by Grochow, Kumar, Saks and Saraf. Bl\"aser et al. gave a
version of an algebraic natural proof barrier for the matrix completion problem
which relies on $\coNP \subseteq \exists \BPP$. It implied that constructing
equations for the corresponding variety should be hard. We generalize their
approach to work with any family of varieties for which the membership problem
is $\NP$-hard and for which we can efficiently generate a dense subset.
Therefore, a similar barrier holds for the slice rank and the minrank
varieties, too. This allows us to set up the slice rank and the minrank
varieties as a test-bed for geometric complexity theory (GCT). We determine the
stabilizers of the tensors that generate the orbit closures of the two
varieties and prove that these tensors are almost characterized by their
symmetries. We prove several nontrivial equations for both the varieties using
different GCT methods. Many equations also work in the regime where membership
testing in the slice rank or minrank varieties is $\NP$-hard. We view this as a
promising sign that the GCT approach might indeed be successful.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2019-11-062019
 Publikationsstatus: Online veröffentlicht
 Seiten: 50 p.
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: arXiv: 1911.02534
URI: http://arxiv.org/abs/1911.02534
BibTex Citekey: Blaeser_arXiv1911.02534
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: