24 problems

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

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

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

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

Circle generator complexity conjecture (strong version). The average circle generator complexity of class algebras is smaller than the corresponding average for fusion algebras:

Let $\mathbb{F}$ be the underlying field, and consider concise tensors in … Write $\sigma(d)$ for the worst-case exponent of this space. Extended asymptotic rank conjecture. For al…

Let $\rK$ be the base field, let $d\in\N$, and let $\cF$ be an $\rsg{d}$ configuration. Write $\Kspan{\cF}$ for its $\rK$-linear span. Strong radical Sylvester–Gallai conjecture. T…

Let $\rK$ be the base field. For $d\in\N$, an $\rsg{d}$ configuration is a configuration $\cF$ of polynomials as defined in the cited formulation of Gupta's conjecture; its transce…

Factor Conjecture. One has

For a polynomial $f$, let $\mathrm{dc}(f)$ denote the least size of a matrix of affine linear forms whose determinant equals $f$. Let $\mathrm{per}_m$ denote the permanent of an…

Let $\mathrm{VBP}$ be the class of polynomial families computable by polynomial-size algebraic branching programs, and let $\mathrm{VNP}$ be Valiant's class of polynomially verifia…

Let $\mathcal{A}$ be an algorithm of length $r$ computing the matrix multiplication tensor $\langle m,n,p\rangle$. Its automorphism group is denoted by $Aut(\mathcal{A})$. Let…

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 $\mathfrak S_m$ denote the permutation group on $m$ elements, let $y^i_j$ be linear coordinates on $\mathbb C^{m^2}$, and define the permanent by … A polynomial-size circuit is…

Constructed-family determinantal lower-bound conjecture. If $a>0$ is small enough, then, with high probability, $f_n$ cannot be expressed as a symbolic determinant of size at most…

Let \textup{\textsf{VPs}} denote the class of polynomial-size algebraic circuits with bounded degree, and let $\textup{\textsf{VNP}}$ denote Valiant's class of efficiently defi…

Symmetric Strassen additivity conjecture.

Let $\mathcal I(\boldsymbol J(\sigma_{r,n},L^S))$ be the ideal of the join of the relevant secant variety $\sigma_{r,n}$ and coordinate linear space $L^S$. A generator is called we…

Fix $0<\epsilon<1$ and $0<\delta<1$. Set $r=\epsilon n$ and $s=n^{1+\delta}$. The notation $\hat{\mathcal R}[n,r,s]$ denotes the relevant matrix rigidity variety, and its irreducib…

Let $\mathbf{k}=\mathbb{R}$ or $\mathbb{C}$, and let $K_0=K_0(\operatorname{sa}_\mathbb{R})$ when $\mathbf{k}=\mathbb{R}$ and $K_0=K_0(\operatorname{Var}_\mathbb{C})$ when…

Mulmuley–Sohoni's strengthened conjecture. For each $c>0$ and infinitely many $n$, $\mathcal{P}erm_n^{n^c}\not\subseteq\mathcal{D}et_{n^c}$. This is a central geometric-complexity-…

Let $K$ be a field of characteristic $\operatorname{ch}(K)$, and let $R_{\delta}(k,s)$ strictly upper-bound the rank of any minimal and simple $\Sigma\Pi_{\delta}\Sigma\Pi(k,s,n)$…