Universality of Computational Lower Bounds for Submatrix Detection

Matthew Brennan, Guy Bresler, Wasim Huleihel

In the general submatrix detection problem, the task is to detect the presence of a small $k\times k$ submatrix with entries sampled from a distribution $\mathcal{P}$ in an $n \ti…