18 problems

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

Let $M$ be an $n\times n$ matrix with entries in $\{0,1\}$ and row sums $d_1,\dotsc,d_n$. Minc's conjecture. The permanent of $M$ is at most … Minc's conjecture was proved by Brégm…

Let $\phi$ be a doubly stochastic $n\times n$ matrix, so that its entries are non-negative and every row and column sums to $1$. The permanent is denoted by…

Barvinok's asymptotic exactness conjecture. There exist a sequence $\{\gamma_d\}$ of non-negative real numbers and, for every $d$ and $\epsilon>0$, a sequence of functions…

Let $W$ be an $n\times n$ matrix with independent entries distributed as $N(0,1)_{\mathbb C}$, and let $p$ be a polynomial in its arguments. Permanent anti-concentration conjecture…

Vu's conjecture. The probability

Let $A$ be a matrix whose entries are independent and identically distributed complex Gaussian random variables. An inverse-polynomial multiplicative error means an error whose rel…

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

Landsberg–Ressayre conjecture. The quantities $\operatorname{\mathsf{edc}}$ and $\operatorname{\mathsf{dc}}$ are polynomially related. If true, this would imply…

Valiant's $\mathbf{VP}_s \neq \mathbf{VNP}$ conjecture. There is no polynomially bounded function $n(m)$ such that $\mathrm{perm}_m$ is a specialization of $\mathrm{IMM}^m_{n(m)}$…

Let $A$ be a $d$-dimensional $(0,1)$-matrix of order $n$. For each $i$, let $r_i$ be the number of ones in the $i$th hyperplane of $A$. Multidimensional permanent upper-bound conje…

Friedland's conjecture. The minimum in the definition of $\alpha(m,n,k)$ can be replaced by an explicitly computable average over a natural distribution $\mu=\mu_{k,n}$ on…

Optimal approximation-factor conjecture. The optimal approximation factor $2^{n/2}$ can be attained by improving the authors' upper bound.

Exponential-size conjecture. Every such construction requires exponential size; equivalently, the dimension of $f(A)$ cannot be bounded by a subexponential function of $n$.

Let $p$ be a non-negative matrix, and let $Z_{o\text{-}f}^{(\gamma)}(p)$ denote the fractional BP partition-function estimate at parameter $\gamma$. In particular, write…

Gurvits's BP upper-bound conjecture. For any non-negative $p$, $f(n)$ is asymptotic to $\sqrt{2}^n$. This conjecture concerns the worst-case multiplicative gap between the permanen…

Exponential critical-ratio conjecture. There is a sequence of constants $\theta_d$ with

Let $A$) be an $n\times n$ matrix with entries in $\{0,1\}$. For a matrix $A$, define $M(A)$ by … where the $\rho_{ij}$ are chosen independently from the Gaussian distribution on…