8 problems

Optimal low-rank covariance approximation conjecture. For almost any positive definite matrix $A$, for every iteration $m\leq n$, there exist $d(m)\ll n$ and $r(d)\leq d(m)$ such t…

Let $\mathcal{L}_2^S\subset\operatorname{Sym}_n(\mathbb{C})$ be the variety of symmetric matrices of rank at most $2$ with diagonal zero pattern $S=\{(1,1),\ldots,(s,s)\}$, where…

Let $\mathcal{L}_2^S\subset\mathbb{C}^{m\times m}$ be the variety of square matrices of rank at most $2$ with zero pattern $S=\{(1,1),\ldots,(s,s)\}$ for some $s\ge2$. Quadratic-gr…

Let $\mathcal{L}_2^S\subset\mathbb{C}^{m\times n}$ be the variety of matrices of rank at most $2$ with diagonal zero pattern $S=\{(1,1),\ldots,(s,s)\}$, where $s\in[4]$, and set…

Assume that $\mathcal{L}_r^S$ is irreducible. Let $I\subset[n]$ satisfy $|I|=m$, and let $X_{[m],I}$ and $U_{[m],I}$ denote the corresponding $m\times m$ submatrices; write…

Let $S evarnothing$ be a zero pattern, let $Uinmathbb{R}^{mtimes n}$, and let $rin[m-1]$. Denote by $Z{U,r}^{S}$ the critical-point variety and by $HU^{S}$ the corresponding affine…

Let $G$ be a $3$-colorable graph on $n$ nodes. Hardness of approximate $3$-coloring. For some fixed $\gamma > 0$, there is no polynomial time algorithm that, given $G$, returns a v…

Let $\boldsymbol{A}$ be a matrix, let $\boldsymbol{A}_k$ be its best rank-$k$ approximation, and let $\boldsymbol{U}_k$ contain the top-$k$ left singular vectors of…