Computational hardness of submatrix localization below the convexified MLE threshold

Let $Y^*$ denote the true support matrix in the submatrix localization model. Assume $\mu\le 1$, $n_L=n_R=n$, $K_L=K_R=K$, and $K\ge c_1\log n$. Submatrix localization computational-hardness conjecture. For every constant $\epsilon>0$, no algorithm with running time polynomial in $n$ can, for all $n$ and with probability at least $1/2$, output $Y^*$ when

$$\mu^2\le\frac{n^{1-\epsilon}}{K^2}.$$

This conjecture asserts that no polynomial-time method substantially improves on the convexified maximum-likelihood estimator, whose recovery boundary is $\mu^2\asymp n/K^2$ up to logarithmic factors; the conjectured gap from the minimax boundary remains open.