29 problems

Mulmuley–Sohoni conjecture. The border width $\underline w(\textup{per})$ grows superpolynomially; equivalently,

Let $g(\lambda,n^d,n^d)$ be a rectangular Kronecker coefficient, and let $\gamma_{\lambda,d,n,m}$ be the multiplicity of the irreducible representation indexed by $\lambda$ in the…

Valiant's hypothesis. The displayed identity is impossible when $d$ is polynomially bounded in $m$. This is a central open problem in algebraic complexity theory and is presented a…

Let $G$ be the ambient special linear group acting on the representation space, and let $G_v$ denote the stabilizer of a complexity-theoretic function $v$. A subgroup is $G$-separa…

Let $G=SL_{n^2}(\mathbb{C})$ and let $H=SL_n(\mathbb{C})\times SL_n(\mathbb{C})$ have its natural embedding in $SL(\mathbb{C}^n\otimes\mathbb{C}^n)$. A subgroup is strongly $G$-sep…

Let $G=SL_{n^2}(\mathbb{C})=SL(\mathbb{C}^n\otimes\mathbb{C}^n)$ and let $H=SL_n(\mathbb{C})\times SL_n(\mathbb{C})$ be embedded naturally by the tensor-product representation. A s…

Let $(f,g)=(\phi(h),g)$ be the pair associated with the arithmetic, nonuniform $P$ versus $NP$ problem, where $n$ is the input-size parameter and $m$ is the circuit-size parameter.…

Let $g=\operatorname{det}(Y)$, $h=\operatorname{perm}(X)$, and $f=\phi(h)$. A strong obstruction is a representation-theoretic obstruction of the type defined in the paper for the…

Let $Y$ be an $m\times m$ variable matrix, let $X$ be an $n\times n$ submatrix with $n<m$, let $g=\operatorname{det}(Y)$, and let $f=\phi(h)$ with $h=\operatorname{perm}(X)$. The a…

Let $v$ be the determinant function and let $Delta_V[v]$ be the class variety associated with $NC$, namely the orbit closure of the determinant. Let $X(Pi_v)$ be the variety and sc…

Extended Mulmuley–Sohoni conjecture. The border width of the permanent grows superquasipolynomially; equivalently,

Let $f$ be the form under consideration, let $f_0$ be its leading form, let $L(\lambda)$ be the Levi subgroup associated with the special one-parameter subgroup $\lambda$, and let…

Let $\mathrm{dc}(\mathrm{per}_m)$ be the determinantal complexity of the $m\times m$ permanent. For integers $d,n,m$, let $\gamma_{\lambda,d,n,m}$ and $\delta_{\lambda,d,n}$ denote…

Let $\ell$ be a linear coordinate on $\mathbb C^1$, and consider a linear inclusion $\mathbb C^1\oplus\mathbb C^{m^2}\rightarrow\mathbb C^{n^2}$. Thus…

Kronecker coefficients are multiplicities arising in representation theory and geometric complexity theory. Kronecker positivity conjecture. Deciding whether a Kronecker coefficien…

Let $U$, $V$, and $W$ be finite-dimensional complex vector spaces, and let the polynomials described by the multilinear-algebra construction for equations of the slice-rank variety…

Occurrence-obstruction conjecture. The vanishing behavior of these multiplicities would be sufficient to separate complexity classes.

Let $\lambda$ be a partition and let $g(\lambda,n\times d,n\times d)$ be the Kronecker coefficient associated with the rectangular partition $n\times d$. Vanishing of this coeffici…

The complexity classes ${\mathsf{VP}}_{ws}$ and ${\mathsf{VNP}}$ are considered through representation-theoretic multiplicities associated with them. Mulmuley–Sohoni multiplicity c…

Let $\lambda \vdash nd$ be a partition, and let $n \times d=(d,d,\ldots,d)$ be the rectangular partition with $n$ rows. For partitions of $nd$, write…

Mulmuley's wild-sequences conjecture. There exist sequences in the closure of the sequences of spaces

Mulmuley's asymptotic Ehrhart conjecture. The multiplicity

Let $G$ be the group acting on the ambient representation space $V$, and let…

Let $W$ be an explicit variety, and distinguish explicit close-to-defining equations from explicit defining equations as in the source. Explicit equations conjecture. (a) Any expli…

Let $W\subseteq K^m$ be an explicit variety. A strict separating e.s.o.p. is a strict separating homogeneous system of parameters for the coordinate ring $K[W]$; for a weakly expli…