English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the variety membership testing problem in the case when the varietyis 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 ofall 3-tensors of slice rank at most $r$. We show that the membership testingproblem for the slice rank variety is $\NP$-hard. While the slice rank varietyis 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 ofmembership 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 Volkand independently by Grochow, Kumar, Saks and Saraf. Bl\"aser et al. gave aversion of an algebraic natural proof barrier for the matrix completion problemwhich relies on $\coNP \subseteq \exists \BPP$. It implied that constructingequations for the corresponding variety should be hard. We generalize theirapproach to work with any family of varieties for which the membership problemis $\NP$-hard and for which we can efficiently generate a dense subset.Therefore, a similar barrier holds for the slice rank and the minrankvarieties, too. This allows us to set up the slice rank and the minrankvarieties as a test-bed for geometric complexity theory (GCT). We determine thestabilizers of the tensors that generate the orbit closures of the twovarieties and prove that these tensors are almost characterized by theirsymmetries. We prove several nontrivial equations for both the varieties usingdifferent GCT methods. Many equations also work in the regime where membershiptesting in the slice rank or minrank varieties is $\NP$-hard. We view this as apromising sign that the GCT approach might indeed be successful.

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