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

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 space 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. We also prove the NP-hardness of membership testing in the minrank variety, establishing 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. We prove that there are no polynomial algebraic natural proofs for testing membership in the slice rank and minrank variety unless coNP is a subset of exists-BPP.

The talk is aimed at the general audience.

computational complexitydiscrete mathematicsalgebraic geometry

Audience: researchers in the topic

( paper | slides | video )

---

LA Combinatorics and Complexity Seminar

Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm

---