13 problems

Let a partial matrix have a bipartite graph whose vertices represent its rows and columns and whose edges represent specified entries. A fully specified submatrix is one in which e…

Let $\mathcal{T}$ be a tensor whose mode-1 unfolding $\mathcal{T}_{(1)}$ is observed on $\Omega_{\mathcal{T}}$, let $M$ be a matrix observed on $\Omega_M$, and let $G$ be the unkno…

Fixed-weight-matrix conjecture. There exists a large constant $\Gamma(\epsilon)>0$ such that every instance $\mathcal{MC}(C,u^*)$ satisfying

Let $\bm H_n=\bm W_{pq}^{n}(\bm W_{pq}^{n})^{\top}$ be the matrix from Theorem, where $\bm W_q^n=\bm V_{\perp}^{n_2}\otimes\bm U_{\perp}^{n_1}$ forms a concentrated sequence of sem…

Let $K_n$ be the complete graph. The $d$-hyperconnectivity matroid $\mathcal H_n^d$ is a $\{K_{d+2},K_{d+1,d+1}\}$-matroid, $\mathcal I_n^2$ is a $\{K_5,K_{3,3}\}$-matroid, and…

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…

Let $G$ be a full-rank typical graph. A $G$-partial matrix is a partial symmetric matrix whose specified off-diagonal entries correspond to the edges of $G$; it is minimally comple…

Let $\operatorname{LS}_n(r,s)$ denote the set of matrices that can be written as the sum of an $n\times n$ matrix of rank at most $r$ and an $n\times n$ matrix with at most $s$ non…

Let $M^*\in\mathcal{S}^{d\times d}$ be symmetric positive semidefinite, and let $\Omega$ be generated under the model $\operatorname{SMC}(M^*,p)$: each $(i,j)$ with $i\geq j$ is ob…

Bipartite circulant generic-rank conjecture. Every graph $G(n,l)$ has generic completion rank predicted by the dimension count; equivalently,

3-core conjecture. The maximal typical rank of $G$ is at least $3$.

Fix a rank $r$ and let $G(n,n,2r,2r)$ denote a uniformly random $2r$-regular bipartite graph with $n$ vertices in each part. A mask is completable when its observed entries determi…

Fix a rank $r$ and let $G(n,n,c/n)$ be the random bipartite graph with edge density parameter $c/n$. Let $t_r$ be the supremum of the constants $t$ for which $G(n,n,t/n)$ is $r$-in…