Exploring Advances in Proof Complexity: Natural Proofs, Algebraic Methods, 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.