76 problems

Valiant's conjecture. The permanent family $(\operatorname{perm}_n)$ does not admit circuits of polynomial size, equivalently,

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

Let $\mathbb{k}$ be the underlying field, and let $T\in\mathbb{k}^a\otimes\mathbb{k}^b\otimes\mathbb{k}^c$ be a tensor that is tight and concise. Here, concise means that the flatt…

Let $K$ be an infinite field, and let $v$ and $w$ be tensors, with $v\boxplus w$ denoting their vertical direct sum. Strassen's additivity conjecture. Tensor rank should satisfy ……

VP versus VNP conjecture.

Let $f$ be a degree-$d$ homogeneous polynomial, and let $\wr{f}$ and $\bwr{f}$ denote its Waring rank and border Waring rank, respectively. The Waring rank is the minimum number of…

Strassen's support-functional conjecture. The asymptotic spectrum of the class of tight tensors coincides with the set of support functionals $\widehat{\zeta}^{\theta}$.

Let $FG$ be a Fibonacci graph, let $Ex(FG)$ be its associated algebraic expression, and measure a representation by the total number of terms and the number of plus operators. 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…

Common-complexity conjecture. The complexity of $K$ for patterns $(G)$, $(S)$, and $(C)$ is the same. Its common value is the inverse of the modulus of the smaller root of

Complex matrix multiplication exponent conjecture.

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 $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…

Bürgisser's conjecture. If the width of $\lambda^{(n)}$ is $\Omega(n^\delta)$ for some $\delta>0$, then the family $(\mathrm{IM}_{\lambda^{(n)}})$ is $\mathrm{VNP}$-complete.

Let $p\ge 2$ be an integer, and let $D_p$ be the degree of the irreducible factor of the elimination resultant for the degree-2 approximation of $(1+t^p)^{1/p}$ on $[0,1]$. Define…

Let $\mathrm{det}_n$ denote the determinant polynomial of degree $n$, and let $\operatorname{str}(\mathrm{det}_n)$ denote its strength. Lampert–Moshkovitz conjecture. The strength…

VFPT versus VW[1] conjecture. There exists a weft-$1$-definable parameterized p-family that is not in $\mathrm{VFPT}$.

Valiant's conjecture. There exists a Boolean-definable sequence $(f_d)_{d\in\mathbb{N}}$ with

Valiant's conjecture. Valiant's conjecture for $R$ is

Let $X$ be an $n\times n$ matrix of indeterminates, and let $I_n$ be the ideal generated by the $\tfrac{n}{2}\times\tfrac{n}{2}$ minors of $X$. For a nonzero polynomial $f\in I_n$,…

Let $\mathbb{F}$ be a field of characteristic zero, and let $f\in\mathbb{F}[x_1,\dots,x_n]$ be computed by an algebraic circuit of size $s$. A polynomial $g$ is a factor of $f$ if…

Let $h(\mathrm{perm}_n)$ and $h(\mathrm{det}_n)$ denote the homological complexities associated with the $n\times n$ permanent and determinant, respectively, and let $\mathcal{VP}$…

Ikenmeyer's conjecture. Christian Ikenmeyer conjectured that this bound holds for any $r$, which would imply the Ballico--Bernardi conjecture. It is known to hold for $r\leq 5$; th…

Average class size conjecture (weak version (b)). The limiting ratio satisfies

Average class size conjecture (strong version). The cumulative ratio satisfies