English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

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

Basic

show hide
Item Permalink: http://hdl.handle.net/21.11116/0000-0005-1D77-6 Version Permalink: http://hdl.handle.net/21.11116/0000-0005-1D78-5
Genre: Paper

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
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. Method: -
 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