38 problems

Pratt's conjecture. For every $\varepsilon>0$,

Simultaneous double product property conjecture. For arbitrarily large $n$, there exists an abelian group $H$ with $n$ pairs of subsets $A_i,B_i$ satisfying the simultaneous double…

Strong USP capacity conjecture. The strong USP capacity equals

Let $k$ be a field, and let $\omega$ be the smallest exponent such that linear algebra on square $n\times n$ matrices over $k$ has complexity $O(n^{\omega+\epsilon})$ for every…

Complex matrix multiplication exponent conjecture.

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

Let $\Pi_d$ be the polynomial set associated with degree-$d$ approximation conditions, and let $\overline{\Pi^*_{2^7}}$ denote the closure of the polynomial set obtainable with sev…

Let $\Pi_d$ be the polynomial set associated with degree-$d$ approximation conditions, and let $\overline{\Pi^*_{2^6}}$ denote the closure of the polynomial set obtainable with six…

Let $\Pi_d$ be the polynomial set associated with degree-$d$ approximation conditions, and let $\overline{\Pi^*_{2^5}}$ denote the closure of the polynomial set obtainable with fiv…

Let $m>2$ and let $\Pi^*_{2^m}$ denote the polynomial set associated with evaluation schemes using $2^m$ matrix-matrix multiplications. Numerical computations suggest that generic…

Let $\omega$ be the exponent of matrix multiplication, defined as the smallest number such that $n \times n$ matrices can be multiplied using $n^{\omega+o(1)}$ arithmetic operation…

For a positive integer $n$, let $[n]=\{1,\ldots,n\}$, and let $s(n)$ denote the largest size of a subset $A\subseteq[n]\times[n]$ containing no non-trivial skew corner, where a ske…

Let $\mathrm{val}(\mathbb Z_n)$ denote the value parameter for the cyclic group $\mathbb Z_n$, as defined in the paper. The near-linear value conjecture. For every $\varepsilon>0$,…

Let $G$ be a finite abelian group, and let $(A_i,B_i)_{i=1}^n$ be pairs of subsets satisfying the simultaneous double product property (SDPP): for each $i$, the equation…

Let $[n]=\{1,\ldots,n\}$, and let $S\subseteq[n]^2$ be skew corner-free, meaning that $S$ contains no three points of the form … with $\delta\ne0$. The skew corner-free set conject…

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…

Exponent-two conjecture. The asymptotic rank of $M_{2,2,2}$ is $4$.

Let $\omega$ be the infimum of all real numbers $\tau$ such that multiplying $\mathbf{n}\times\mathbf{n}$ matrices can be done using ${\mathcal O}(\mathbf{n}^{\tau})$ arithmetic op…

Matrix multiplication exponent conjecture.

Let $\omega$ denote the infimum of the exponents $\tau$ such that $n\times n$ matrices can be multiplied using $\mathcal O(n^\tau)$ arithmetic operations. Classically,…

Exponent-two conjecture. It is generally conjectured that

Let $\omega$ denote the exponent of matrix multiplication, equivalently the asymptotic exponent governing the border rank of the matrix multiplication tensors. Exponent-two conject…

Let a matrix approximation be specified by the powers of two used for its nonzero entries and by the locations of those entries. For a $K\times K$ matrix with $NK$ nonzero entries,…

Let $\omega$ denote the exponent of matrix multiplication, the fundamental constant governing the complexity of multiplying square matrices. Matrix multiplication exponent conjectu…

Let $\omega$ be the smallest real number such that two $n \times n$ matrices over a field can be multiplied using $n^{\omega + o(1)}$ field operations. The exponent-two conjecture.…