5 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

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…