![Meta-complexity_logo_hi-res](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-02/Meta-complexity_hi-res.png.jpg?itok=oFqprXq1)
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. 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.