Finding a Large Submatrix of a Random Matrix, and the Overlap Gap Property
summary
Random n×n Gaussian matrix has an explicit asymptotic optimum for the largest k×k submatrix average given by a tail/extreme-value moment calculation; naive greedy/threshold approaches reach only the smaller log‑n/k scale. A simple sequential greedy procedure (grow one row/column at a time) provably improves that baseline by a factor 4/3 but still misses the global optimum (about √2 times the baseline). Analysis uses first/second moment and extreme‑value/Gaussian tail estimates and uncovers an overlap gap property—a forbidden overlap range that disconnects high‑value solutions and explains why local algorithms fail.
AI-written summary · about