3 problems

Sub-tensor phase-transition conjecture. Extending the main theorem to the tensor setting should reveal new phenomena in sub-tensor detection, in particular new phase transitions de…

Computational-gap conjecture. Constraining detection to polynomial-time testing procedures should lead to suboptimal statistical performance in this regime.

Let $p=2$, and let the Large Average Submatrix algorithm, denoted by $\mathcal{LAS}$, start from a uniformly random $k\times k$ submatrix of an $n\times n$ random matrix. A local o…