This posts summarizes some my favorite open problems about the nonnegative rank of matrices and related concepts like extension complexity of polytopes (
see this post.)
Some notation & terminology:
$\mbox{frk}_S$ | factorization rank over the semiring S |
$\mbox{ndCC}(A)$ | nondeterministic communication complexity of the support of A |
$\mbox{fool}(A)$ | fooling set bound |
Theoretical questions
- Cohen & Rothblum (1993) asked: If ${A}$ is rational, is its factorization rank over ${\mathbf{Q}_+}$ equal to the factorization rank over ${\mathbf{R}_+}$? More generally: If ${A}$ has entries in a sub-semiring ${S}$ of a sub-semiring ${R}$ of the nonnegative reals, how large can the gap be between ${\mbox{frk}_S(A)}$ and ${\mbox{frk}_R(A)}$? (Beasley & Laffey 2009)
- Given any sub-semiring ${S}$ of ${\mathbf{R}_+}$ and ${n\ge 6}$, is there a matrix ${A \in \mathbf{M}_{n\times n}(S)}$ such that ${\mbox{rk} A = 3}$ and ${\mbox{frk}_S(A) = n}$? (Beasley & Laffey 2009) This is open even for ${S=\mathbf{R}_+}$. Cf. Specific-Question #1.
- If ${A}$ is a symmetric ${n\times n}$ nonnegative matrix with real rank ${k}$, and if ${A}$ has exactly one negative eigenvalue, must ${A}$ have a nonnegative factorization ${A = XY}$ where ${X}$ is ${n\times q}$ with ${q}$ bounded as a function of ${k}$? (Beasley & Laffey 2009)
- What is the smallest $\alpha$ such that $\mbox{rk}_+(A) \le \mbox{rk}(A)^\alpha$ for all 01-matrices $A$? This corresponds to LovĂˇsz and Saks log-rank conjecture (with $\alpha = \infty$ if that is false). Proving lower bounds for $\alpha$ corresponds to proving lower bounds for the nonnegative rank.
- What is the largest separation between the logarithm of the nonnegative rank and the deterministic communication complexity for Boolean functions? The gap cannot be more than quadratic, but the best known example has a smaller gap. A related question asks for the largest separation between the nonnegative rank and the biclique covering number for 01-matrices.
- It is known that ${\displaystyle \mbox{fool}(A) \le (\mbox{rk} A)^2}$. (Dietzfelbinger Hromkovic Juraj Schnitger (1996)), and there are examples where ${\mbox{fool}(A) \ge (\mbox{rk} A)^{\log_3 4}}$. Which of these two bounds can be improved? (Dietzfelbinger, Hromkovic, Juraj, Schnitger 1996)
Questions about specific families of matrices
- A ${d}$-dimensional, Euclidean distance Matrix of size ${n}$ is defined by points ${x_1,\dots,x_n}$ in ${d}$-dimensional Euclidean space. Its entries are ${\bigl( \lVert x_k - x_\ell \rVert )_{k,\ell}}$. Do ``generic''/``random'' Euclidean distance Matrices have full nonnegative rank? (Gillis & Glineur 2011; Lin & Chu 2010). A proof of this for ${d=1}$ by Lin & Chu 2010 is fatally flawed. More spcifically: Do some linear Euclidean distance Matrices have the propery asked for in Theory-Question #2? (Beasley & Laffey 2009) (Not all of them do (Gillis & Glineur 2011).)
The rank bound and the ndCC bound are both trivial for these matrices. Upper bounds for special cases have been improved. (Gillis & Glineur 2011)
- Does a random (with a suitable distribution) ${(m\times n)}$ rank-${k}$ matrix have full nonnegative rank? A weaker question asked by J. Garcke, M. Klimm, H.-C. Kreusler, and A. Uschmajew is: Has the set of matrices with nonnegative rank-${k}$ has positive Lebesgue measure within the ${(m\times n)}$ rank-${k}$ matrices? If ${A}$ is randomly drawn from the ${(m\times n)}$-matrices with nonnegative rank ${k}$, is ${\mbox{rk} A = k}$ with probability one / positive probability? (Dong, Lin, Chu)
For some of these questions, erroneous proofs can be found on the internet. In particular, a proof by Dong, Lin, and Chu is incorrect. The rank bound and the ndCC bound are both trivial for these matrices.
- Is the extension complexity of the Matching Polytope of an ${n}$-vertex graph polynomial in ${n}$?
An infamous, several decades old question in Combinatorial Optimization asks, whether there exist an extended formulation for the matching problem whose coding size is polynomial in the number of vertices of the graph. A slightly weaker question asks whether there exist an extended formulation whose number of inequalities is bounded by a polynomial in the number of vertices of the graph. The best known lower bound is the trivial rank bound ${\Omega(n^2)}$. The ndCC bound is ${O(n^4).}$ The known upper bounds are ${O(c^n)}$, for values of ${c\in \left]1,2\right]}$ which have been improved several times in the last three decades.
- Is the extension complexity of the Spanning Tree polytope ${\Omega(n^3)}$?.
Michele Goemans asked this question at the Cargese Workshop on Combinatorial Optimization 2010, which was dedicated to extended formulations. The best known lower bound is the trivial rank bound. It is unknown whether the ndCC bound improves on the rank bound. The known upper bound is ${O(n^3)}$, with improvements for certain types of graphs.
- What is the extension complexity of the Stable Set polytope of a perfect graph?
The question goes back to Yannakakis (1991), and was recently repeated by Michele Goemans (MIT) at the Cargese Workshop on Combinatorial Optimization 2010, which was dedicated to extended formulations.
- Is the extension complexity of the Completion Time polytope ${O(n\log n)}$? (Goemans 2011 & Cargese)
If true, this would extend work by Goemans (2011). The best known lower bound is the trivial rank bound. The upper bound is ${O(n^2)}$, which has been proved in a couple of ways in the last 20 years.
- Is the extension complexity of an ${n}$-vertex convex polygon with vertices in general position ${\Omega(n)}$? (Fiorini, Rothvoss, Tiwary) The rank bound is 2, the ndCC bound is ${\Omega(\log n)}$. Some regular convex polygons have extension complexity ${\Theta(\log n)}$. The best known lower bound for algebraically independent vertices is ${\Omega(\sqrt n)}$.