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

Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, Frank-Olaf SchreyerarXiv 2019 · OpenReview

TL;DR

This paper tackles the computational complexity of determining if a given tensor belongs to specific algebraic varieties, namely the "slice rank" and "minrank" varieties. The authors prove these problems are NP-hard, establishing a barrier for algebraic circuit lower bounds and proposing these varieties as test cases for Geometric Complexity Theory (GCT).

What Problem Does This Paper Address?

The paper investigates the complexity of "variety membership testing" in algebraic geometry. Specifically, it focuses on varieties defined by orbit closures of tensors, which are fundamental objects in areas like matrix multiplication and algebraic complexity. The core challenge is to determine if a given tensor falls within a specific variety. This is crucial for understanding the inherent difficulty of computational problems related to these algebraic structures. The authors highlight that while membership testing for varieties defined by polynomial equations is generally easy (polynomial-time equivalent to arithmetic circuit identity testing), the complexity changes dramatically when varieties are defined as orbit closures, especially for tensors. They aim to shed light on the hardness of these orbit closure problems and their implications for proving fundamental complexity lower bounds.

Methods

The paper employs a combination of techniques from algebraic geometry, representation theory, and complexity theory.

  • NP-Hardness Proofs: The authors establish NP-hardness for slice rank and minrank variety membership testing through reductions from hypergraph vertex cover and a bounded-occurrence mixed SAT problem (bom-SAT). This involves constructing specific tensor gadgets that encode the combinatorial problems.
  • Geometric Complexity Theory (GCT): The paper leverages GCT, a framework aiming to prove lower bounds in algebraic complexity by studying orbit closures and their symmetries. They analyze the stabilizers of tensors that define these orbit closures.
  • Representation Theory: Techniques from representation theory, particularly concerning irreducible representations of general linear groups and Kronecker coefficients, are used to construct equations for the varieties.
  • Algebraic Natural Proofs: The authors generalize the concept of algebraic natural proofs to establish barriers for constructing polynomial-size algebraic circuits for equations defining these varieties, especially when membership testing is NP-hard.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Slice Rank and Minrank are Hard: The paper proves that determining if a 3-tensor has a slice rank or minrank below a certain threshold is NP-hard. This is a significant result as it implies these problems are computationally difficult.
  • Orbit Closures as a Barrier: The NP-hardness of membership testing in minrank varieties (which are orbit closures) directly leads to the NP-hardness of the orbit closure containment problem. This is a fundamental problem in algebraic complexity.
  • GCT as a Promising Framework: The paper positions the slice rank and minrank varieties as valuable "test beds" for GCT. The NP-hardness of membership testing, combined with the ability to generate dense subsets of these varieties, allows for the application of algebraic natural proof barriers. This suggests GCT might offer a path to proving lower bounds where other methods have struggled.
  • Symmetries Reveal Structure: The authors show that the tensors defining these orbit closures are "almost characterized by their symmetries." Understanding these symmetries is key to finding equations for the varieties, a central goal in GCT.
  • Equations from Representation Theory: The paper demonstrates how representation theory can be used to derive nontrivial equations for these complex varieties. This provides a constructive approach within the GCT framework.

Key Results

  • NP-Hardness: The slice rank variety membership problem is proven to be NP-hard.
  • NP-Hardness: The minrank variety membership problem is proven to be NP-hard.
  • Orbit Closure Containment: As a consequence, the orbit closure containment problem for 3-tensors is shown to be NP-hard.
  • Algebraic Natural Proof Barriers: The paper generalizes algebraic natural proof barriers to varieties with NP-hard membership problems, showing that not all equations defining these varieties can have polynomial-size algebraic circuits (unless coNP ⊆ ∃BPP).
  • Equations for Varieties: The authors construct several nontrivial equations for both the slice rank and minrank varieties using GCT methods, including representation-theoretic approaches and Koszul flattenings.

Limitations and Future Work

  • Open Questions: The paper notes that the complexity of the tensor rank problem itself remains unknown, though it's suspected to be hard.
  • GCT Applicability: While the paper shows promise for GCT by establishing NP-hardness and constructing equations, it acknowledges that proving lower bounds for problems like the permanent versus determinant remains a significant challenge.
  • Finding Concrete Tensors: The authors express a desire to find explicit, nontrivial tensors for which slice rank or minrank lower bounds can be proven using the derived equations.
  • Hyperdeterminant: The paper mentions an open question regarding whether the hyperdeterminant vanishes on the matrix multiplication tensor.

Summary updated

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.
BibTeX
@misc{blaser2019variety,
  author = {Markus Bläser and Christian Ikenmeyer and Vladimir Lysikov and Anurag Pandey and Frank-Olaf Schreyer},
  title = {{Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory}},
  year = {2019},
  eprint = {1911.02534},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.02534},
}
Figure