11 problems

Let $D(\mathcal{S})$ denote the density operators supported on an $r$-dimensional subspace $\mathcal{S}\subseteq\mathbb{C}^n$, and let $K_{n,r}$ be the suboptimality ratio defined…

Approximate Duality Conjecture. If $D_\omega(A,B)\geq\varepsilon$ for some $\varepsilon>0$, then there exist subsets $A'\subseteq A$ and $B'\subseteq B$ such that…

Lovett's incidence-graph conjecture. If the graph has at least $(1-\varepsilon)n^2$ edges, then it contains a complete balanced bipartite subgraph of size at least

Lovett's conjecture. The matrix $M$ contains an all-zero square submatrix of size at least

Further asymptotic minimization conjecture. With a presumably possible weakening of the nestedness assumption, the limit of $X_\gamma$ will, almost always, additionally minimize…

Let ${\cal M}$ be a pattern matrix under the paper's standing Assumption, and let $k\geq 1$. The problem $\operatorname{GLRMC}({\cal M},k)$ asks whether, for almost all values of t…

Finite-completion conjecture. Without loss of generality, let the number of $1$'s at every row and column of $\Omega$ be at least $r+1$. Then a generic rank-$r$ matrix $X$ observed…

Recall that ${\mathcal M}_{d,r}({\mathbb F})$ denotes the set of $d\times d$ matrices over ${\mathbb F}$ with rank at most $r$. Let ${\mathcal A}=(A_j)_{j=1}^N$ be a collection of…

Uniform lower-bound conjecture. For any fixed rank $r$, $lambda_{min}$ is larger than a fixed constant for all states of rank $r$, regardless of the number of ions.

Reduced settings hypothesis. For Pauli measurements, the MSE of low-rank states should concentrate when only a small number of measurement settings is used.

Let $\mathcal{M}$ be a matrix subspace that is promised to be spanned by rank-one matrices, although those matrices are not necessarily given. The rank-one basis problem asks for a…