Item

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.