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