The completability-transition conjecture for random bipartite masks

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$-independent with high probability, and let the $(r+1)$-core be the maximal subgraph of minimum degree at least $r+1$. A mask is completable when its observed entries determine a generic rank-$r$ matrix, and the completability transition is the threshold for this property. Completability-transition conjecture. The constant $t_r$ is the threshold for the completability transition in $G(n,n,c/n)$. Moreover, almost all of the $(r+1)$-core is completable above the threshold. This includes the conjecture that the completability threshold exists; the paper notes that this has not been established, unlike the threshold for the emergence of a circuit. The claim is supported by experiments and is compared with results for two-dimensional distance matrices.