Consider an N ×N symmetric Gaussian matrix, with a hidden k×k planted principal submatrix with elevated mean λ/N. We set k = N ρ, and study support recovery for the submatrix using the MLE. Under the double asymptotic regime ρ → 0 following N → ∞, we provide evidence for a computationally hard phase by exhibiting that the likelihood landscape exhibits a version of the Overlap-Gap-Property.

This is based on joint work with David Gamarnik and Aukosh Jagannath.