English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  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

Files

show Files
hide Files
:
arXiv:1911.02534.pdf (Preprint), 613KB
Name:
arXiv:1911.02534.pdf
Description:
File downloaded from arXiv at 2019-11-15 10:59
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

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

Content

show
hide
Free keywords: Computer Science, Computational Complexity, cs.CC,Mathematics, Algebraic Geometry, math.AG,Mathematics, Representation Theory, math.RT
 Abstract: 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

show
hide
Language(s): eng - English
 Dates: 2019-11-062019
 Publication Status: Published online
 Pages: 50 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1911.02534
URI: http://arxiv.org/abs/1911.02534
BibTex Citekey: Blaeser_arXiv1911.02534
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show