Erba, VittorioKrzakala, FlorentPerez Ortiz, RodrigoZdeborova, Lenka2024-02-212024-02-212024-02-212024-01-0110.1088/1742-5468/ad1391https://infoscience.epfl.ch/handle/20.500.14299/205100WOS:001144934900001We study the maximum-average submatrix problem, wherein given an N x N matrix J, one needs to find the k x k submatrix with the largest average number of entries. We investigate the problem for random matrices J, whose entries are i.i.d. random variables, by mapping it to a variant of the Sherrington-Kirkpatrick spin-glass model at fixed magnetisation. We analytically characterise the phase diagram of the model as a function of the submatrix average and the size of the submatrix k in the limit N → ∞. We consider submatrices of size k=mN with 0<m<1 . We find a rich phase diagram, including dynamical, static one-step replica symmetry breaking (1-RSB) and full-step RSB. In the limit of m -> 0, we find a simpler phase diagram featuring a frozen 1-RSB phase, where the Gibbs measure comprises exponentially many pure states each with zero entropy. We discover an interesting phenomenon, reminiscent of the phenomenology of the binary perceptron: there are efficient algorithms that provably work in the frozen 1-RSB phase.TechnologyPhysical SciencesCavity And Replica MethodPhase DiagramsTypical-Case Computational Complexitytext::journal::journal article::research article