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

Markus Bläser (Saarland University) https://simons.berkeley.edu/talks/markus-blaser-saarland-university-2023-03-22-0 Proof Complexity and Meta-Mathematics 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. We prove that testing membership in the slice rank and minrank variety is NP-hard. Hence we establish the NP-hardness of the orbit closure containment problem for 3-tensors. Algebraic natural proofs were introduced by Forbes, Shpilka and Volk and independently by Grochow, Kumar, Saks and Saraf. Bläser et al. gave a version of an algebraic natural proof barrier for the matrix completion problem. 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. This allows us to set up the slice rank and the minrank varieties as a test-bed for geometric complexity theory (GCT). We prove several nontrivial equations for both the varieties using different GCT methods.