The Overlap Gap Property in Principal Submatrix Recovery

Aukosh Jagannath; David Gamarnik; Subhabrata Sen

REVIEW 3 major objections 4 minor 81 references

The Overlap Gap Property in Principal Submatrix Recovery

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The planted submatrix model has an overlap gap at moderate signal strengths, making the likelihood landscape disconnected in overlap and forcing reversible local MCMC samplers to take exponential time to reach high-overlap configurations.

desk verdict Rigorous OGP for planted submatrix recovery is a real step forward, but the zero-temperature variational proof has a visible factor-2 mismatch that must be fixed before the main theorem holds up. read the letter →

arxiv 1908.09959 v2 pith:WKDOXQ3X submitted 2019-08-26 math.PR cs.CCmath.STstat.TH

David Gamarnik , Aukosh Jagannath , Subhabrata Sen This is my paper · ORCID

classification math.PRcs.CCmath.STstat.TH MSC 68Q8760C0582B4468Q2562H25

keywords overlapgappropertyprincipalsubmatrixrecoveryspinglassesParisiformulastatistical-computationalMarkovchainMonteCarloapproximatesupportspectralmethod

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies a planted principal submatrix problem: an $N\times N$ Gaussian matrix contains a hidden $k\times k$ submatrix ($k=\rho N$) with elevated mean $\lambda/N$, and the goal is to recover a constant fraction of its support. The authors establish that approximate recovery by the maximum likelihood estimator is possible exactly when $\lambda$ is at least a constant times $\sqrt{(1/\rho)\log(1/\rho)}$, and impossible below that scale. Their main discovery, however, is about the likelihood landscape: in the high-sparsity, moderate-signal window $\sqrt{(1/\rho)\log(1/\rho)} \ll \lambda \ll \rho^{-\alpha}$ for $\alpha<2-\sqrt{2}$, the constrained energy has a local maximum at a suboptimal overlap, so near-optimal configurations split into well-separated low- and high-overlap clusters. They prove this overlap gap property implies that local reversible Markov chains, started at a random overlap, require exponential time to reach the good cluster. A straightforward rounding of the top eigenvector succeeds once $\lambda>1/\rho$, showing the barrier sits between the information-theoretic and spectral regimes.

What carries the argument

The load-bearing object is the constrained ground state energy $E(q;\rho,\lambda)=\lim_{N\to\infty}\frac{1}{N}\max\{(x,Wx)+\lambda q^2 : x\in\Sigma_N(\rho N),\,(x,v)=Nq\}$. Theorem 2.1 evaluates this limit as $\lambda q^2+\min_{\nu,\Lambda}P(\nu,\Lambda)$, a Parisi-type variational formula over monotone measures $\nu$ and Lagrange multipliers $\Lambda$; the PDE in the formula is solved through a family of diffusions. The proof of OGP comes from differentiating this functional: at $q=\rho^2$ the derivative is $2\lambda\rho^2>0$, while at $q=\rho^{2-\delta}$ the derivative is negative for the claimed parameter range, forcing an interior local maximum and hence the gap. The SDE representation and the bound $\int_0^\rho m(t)\,dt \le \frac{1}{2}\sqrt{\rho\log(1/\rho)}$ control the derivative and complete the sign-change argument.

What would settle it

Compute $E(q;\rho,\lambda)$ from the variational formula for a concrete pair inside the claimed window, say $\rho=10^{-3}$ and $\lambda=10\sqrt{(1/\rho)\log(1/\rho)}$, and check the sign of $\partial_q E$ at $q=\rho^2$ and at $q=\rho^{2-\delta}$ with $\delta\approx 0.2$; if the derivative is nonnegative at $q=\rho^{2-\delta}$, or if the energy curve has no interior local maximum between $\rho^2$ and $\rho^{1+\varepsilon}$, then the overlap gap property, and with it the exponential hitting-time bound, fails exactly where Theorem 1.4 claims it holds.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is Theorem 1.4: for any $\alpha<2-\sqrt{2}$, any $C_1>2$, all sufficiently small $\rho$, and all $\lambda$ with $C_1\sqrt{(1/\rho)\log(1/\rho)}<\lambda<\rho^{-\alpha}$, the planted submatrix model has the $\varepsilon$-overlap gap property. That means there are overlaps $w<\rho^2<x<y<\rho^{1+\varepsilon}$ at which the constrained ground state energy $E(q;\rho,\lambda)$ satisfies $E(w)<E(x)$ and $E(y)<E(x)$, with the supremum over the interval $(w,\varepsilon\rho]$ strictly below the supremum over $[\varepsilon\rho,\rho]$. The likelihood landscape is therefore disconnected along the overlap axis: any near-maximizer is either nearly uncorrelated with the planted vector or strongly correlated with it, never in between. Combining this structural statement with the free-energy-well argument gives Theorem 1.5: a reversible nearest-neighbor Markov chain on the Hamming graph, initialized from the Gibbs measure conditioned on the low-overlap interval, has exponentially small probability of escaping that interval before time $\exp(cN)$.

Load-bearing premise

The argument depends on the claim that the rescaled maximum-likelihood value at every fixed overlap is exactly described by a tractable mean-field variational formula; if that formula is wrong for any overlap between the trivial solution and the good solution, the disconnectedness of the landscape and the sampling barrier both vanish.

Editorial extensions

If this is right

Approximate support recovery is information-theoretically possible in the whole OGP window, yet no reversible local MCMC algorithm can achieve it in polynomial time from a random start; the gap between statistical possibility and local algorithmic success is rigorous, not conjectural.
The threshold for the MLE is sharp up to a constant factor: recovery succeeds for $\lambda>(2+\varepsilon)\sqrt{(1/\rho)\log(1/\rho)}$ and fails when $\lambda=o(\sqrt{(1/\rho)\log(1/\rho)})$.
For $\lambda>1/\rho$, rounding the leading eigenvector of $A$ recovers a constant fraction of the support, so the hard phase sits strictly between the information-theoretic threshold and the spectral threshold.
As a by-product, the first-order asymptotics of the largest sum of entries over all $N\rho\times N\rho$ principal submatrices of an i.i.d. Gaussian matrix is determined by the value $E(\rho^2;\rho,0)/\sqrt{2}$.
The barrier becomes more pronounced as $\rho\to 0$: the difficult window in $\lambda$ widens with sparsity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same derivative-sign analysis should extend the overlap gap to the full sub-spectral window $\sqrt{(1/\rho)\log(1/\rho)} \ll \lambda \ll 1/\rho$; the paper stops at $\rho^{-\alpha}$ for $\alpha<2-\sqrt{2}$ only because the current scaling estimates degrade there, and such an extension would make the hard phase coincide with the conjectured computational threshold.
The free-energy-well argument never uses the detailed-balance reversibility beyond Theorem 3.2; only the overlap's Lipschitz property and the exponential concentration of the Gibbs weights are needed, so the barrier should apply to any local search whose stationary distribution is approximately Gibbs, including simulated tempering or parallel tempering variants.
A numerical evaluation of the variational formula for finite $\rho$ (for example $\rho=10^{-3}$) could chart the finite-size precursor of the gap and may show the OGP appears already at moderate $N$, providing a direct test of the proof's scaling predictions.
For the $k=o(N)$ sparse PCA analogue, the same two-species Lagrange-multiplier decoupling is a natural starting point for an overlap-gap proof, suggesting the barrier found here is not an artifact of the constant-density constraint.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper makes a genuine advance: it proves the first rigorous overlap gap property for the planted submatrix model in the constant-ρ, ρ→0 regime, and it extracts a clean MCMC barrier from that OGP. The information-theoretic threshold for the MLE and the spectral rounding for λ > 1/ρ are also solid. The two-species Parisi-type variational formula is a substantial piece of work, not a routine import.

The soft spot is real and it sits right at the load-bearing joint. In Section 4.1, the functionals Eβ and E are displayed with the linear term −∫ s dν(s), while the finite-temperature functional (4.3) and the target P in Theorem 2.1 both carry −2∫ s dν(s). The proof of Lemma 4.4 never addresses this term, so if the Γ-convergence statement is taken at face value, the limit is the wrong functional. That would change the derivative of E(q) and the sign of ∂q E at ρ²−δ, which is exactly what creates the OGP gap. It may be a typo, but it is not a harmless one; the authors need to correct the display and verify that the Γ-limit recovers the factor 2.

The second concern is related: the Γ-convergence result is imported from [50], which is single-species, and the paper asserts the extension to two species with different terminal data in a few lines. The atom at ρ is handled by a linear transformation, but the recovery sequence from [50, Lemma 3.4] is not shown to work for both species simultaneously. Lemma 6.4 (the Ghirlanda–Guerra perturbation) is also only sketched, and the embedding of the constrained two-species model into the ultrametric framework is not fully detailed.

If those gaps are repairable, this is an important paper. As written, I would not rely on Theorem 1.4 without a careful check of Section 4.1. The information-theoretic and spectral parts stand on their own.

Recommendation: yes, send it to peer review — this is exactly the kind of paper a serious referee should spend time on — but the referee's first job is to resolve the factor-2 mismatch. I wouldn't cite the OGP result in my own work until that is settled.

Referee Report

3 major / 4 minor

Summary. The paper studies approximate support recovery in the planted principal submatrix model A = (λ/N)vv^T + W, where W is a GOE matrix, v has density ρ, and λ is a constant. The main results are: (i) an information-theoretic threshold at λ ≈ sqrt((1/ρ) log(1/ρ)) for approximate recovery, with MLE optimal up to constants; (ii) an ε-overlap-gap property (OGP) for the constrained maximum likelihood energy E(q;ρ,λ) in the window C1 sqrt((1/ρ) log(1/ρ)) < λ < ρ^{-α} for α < 2 - sqrt(2) and ρ small; (iii) a consequence that a natural family of local reversible MCMC samplers requires exponential time to leave the low-overlap region; and (iv) a spectral algorithm achieving approximate recovery when λ > 1/ρ. The central technical engine is a Parisi-type variational formula for E(q;ρ,λ), obtained as a zero-temperature limit of a two-species spin glass free energy, followed by a delicate analysis of the derivative of E with respect to q using SDE representations and quantile bounds.

Significance. If the main theorem is fully established, the paper would be a significant contribution to the statistical-computational gap literature: it gives structural landscape evidence for hardness in sparse PCA / planted submatrix recovery, connects to the OGP framework, and provides a clean algorithmic consequence for local MCMC. The information-theoretic threshold and the spectral result are also useful. The proof strategy is sophisticated: it combines Guerra interpolation, Aizenman-Sims-Starr bounds, Ghirlanda-Guerra identities, ultrametricity, and a zero-temperature Γ-convergence result imported from the authors' prior work. The paper is honest about relying on this machinery, but the missing verification of the two-species zero-temperature Γ-convergence and some visible factor inconsistencies mean the central claim is currently not fully supported as written. The result is plausible and the high-level strategy is credible, but a careful repair of the variational proof is needed before the paper can be accepted.

major comments (3)

[Section 4.1, Lemma 4.4 and Theorem 4.2] There is a factor-of-two mismatch in the functionals used for the zero-temperature limit. The finite-temperature functional Pβ in (4.3) and the target functional P in Theorem 2.1 both contain the linear term −2∫ s dν(s), whereas the functionals Eβ and E defined immediately before Lemma 4.4 contain −∫ s dν(s). As written, Lemma 4.4 proves Γ-convergence to a functional that is not the one appearing in Theorem 4.2 or Theorem 2.1. Since Theorem 2.1 is the foundation for the derivative estimates in (2.9)–(2.10) that produce the overlap gap, this discrepancy is load-bearing. The authors should either correct the coefficient and re-check the subsequent compactness and convergence arguments, or explicitly explain a change of variables that removes the factor of two.
[Section 4.1, Lemma 4.4 and Section 6.2] The extension of the zero-temperature Γ-convergence result to the two-species constrained functional is asserted rather than proved. The imported result [50, Theorem 3.2] is for a single Parisi functional, while here the same measure ν must simultaneously recover the limits for two species with different terminal data Λ1 and Λ2, and the limiting measure may require treatment of atoms after the c=0 reduction in Section 2. The claim in the proof of Lemma 4.4 that the recovery sequence 'does not depend on the functional itself' is not sufficient, because the minimizer of the sum is not automatically a recovery sequence for both summands. This is not a cosmetic gap: if the Γ-convergence fails for some q in the critical interval, the sign changes of ∂_q E that create the gap collapse. Please provide a detailed proof of Lemma 4.4 or a precise citation to a two-species version of the Γ-convergence theorem.
[Section 5, Lemmas 5.2 and 4.6] The displayed chain in the proof of Lemma 4.6 appears algebraically inconsistent with the derivative formula in Lemma 5.2. Lemma 5.2 states ∂βF = 2β∫(ρ²−q²)dµ(q), but the proof of Lemma 4.6 writes β∫(ρ−q)dµ(q) ≤ (1/(4ρ))β∫(ρ²−q²)dµ(q) = (1/(4ρ))∂βF. Combining these identities gives a right-hand side of (1/(8ρ))∂βF after the displayed inequality, not (1/(4ρ))∂βF, and the inequality itself does not follow from (ρ−q) ≤ (ρ²−q²)/(ρ+q). Since Lemma 2.2's constant (1/2)√(ρ log(1/ρ)) enters the quantile bounds (2.9) and hence the OGP window, this factor must be reconciled. Please re-derive the constants in Lemmas 5.2 and 4.6 carefully.

minor comments (4)

[Section 4.1, Lemma 4.4] The phrase 'with minor modification' is too terse for a step that carries the entire zero-temperature limit. Even if the factor issue is resolved, the lemma deserves a full proof or a precise statement of the modified assumptions under which [50] applies.
[Section 6.2.2, Lemma 6.4] The Ghirlanda-Guerra perturbation argument is only sketched. The paper correctly notes that the self-overlap R11 is constant on Σ_N(ρ,q), which removes the usual self-overlap terms, but the construction of the parameters (x_p) and the verification of the identities should be written out or quoted more explicitly.
[Section 2, proof of Theorem 1.4] The notation q = ρ²−δ is easy to misread as ρ² − δ; it should be typeset consistently as ρ^{2−δ}. The displayed derivative bound surrounding (2.10) also contains an unmatched parenthesis that should be fixed.
[Section 3, Theorem 3.3] The condition y = o_ρ(ρ) in Theorem 3.3 is consistent with Definition 1.3 only after taking ρ → 0 with ε fixed; this quantifier should be stated explicitly to avoid apparent conflict with the condition y < ρ^{1+ε}.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1.4 is derived from an in-paper variational analysis, and the self-cited Gamma-convergence from [50] is external mathematical support rather than a restatement of the target result.

full rationale

The derivation chain for the overlap gap property is: Theorem 2.1 gives the constrained ground-state energy E(q;rho,lambda) as a Parisi-type variational formula; the proof then differentiates this formula, uses the stochastic representation (2.7), bounds the quantiles in (2.9), and combines with Lemma 2.2 to show sign changes of the derivative of E. That part is worked out in the paper. Theorem 2.1 is in turn obtained from the finite-temperature free energy formula (Proposition 4.1), proved by Guerra interpolation and the ASS scheme in Section 6, and the zero-temperature limit (Theorem 4.2). The zero-temperature limit imports [50, Theorem 3.2] for Gamma-convergence of the nonlinear Parisi term, along with several technical lemmas from [50]. These citations are to the authors' own prior work, but the cited statements concern general Parisi functionals, not the overlap gap property or the principal submatrix model, and they do not assume the present conclusions; they are parameter-free analytic facts. The short extension to the two-species constrained functional in Lemma 4.4 is a mathematical gap risk, as is the possible factor discrepancy in the linear - integral s dnu(s) term in Section 4.1, but a missing or under-verified proof step is a correctness issue, not circularity: no quantity in Theorem 1.4 is defined in terms of the overlap gap property, and no parameter is fitted to the data being predicted. Consequently, the central claim is not equivalent by construction to its inputs, and the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper is a pure mathematical derivation with no data fitting. The constants in the theorems are universal and existentially quantified. The main axioms are standard theorems of mean-field spin glass theory; several are quoted from the authors' own prior work but are general results independent of the planted submatrix setting.

assumptions (5)

standard math Parisi-type free energy formulas for mean-field spin glasses (Guerra interpolation, Panchenko's theorems)
Invoked in Section 6 to compute the finite-temperature free energy of the two-species constrained SK model (Proposition 4.1).
standard math Zero-temperature Γ-convergence of Parisi-type functionals as in Jagannath-Sen [50]
Used in Section 4.1 to take β→∞ and obtain the ground-state variational formula (Theorem 4.2). This is a self-cited general result about Parisi functionals, independent of the planted submatrix model.
standard math Ghirlanda-Guerra identities and ultrametricity of overlap distributions (Panchenko 2013, Talagrand)
Used in Section 6.2.2 to pass from the Gibbs measure to Ruelle probability cascade overlap structures in the Aizenman-Sims-Starr lower bound.
standard math Slepian comparison inequality and Gaussian concentration of maxima
Used in Section 2 (equation 2.11) and Section 5 to bound the maximum of the Gaussian quadratic form and to prove Lemma 4.6.
standard math Ruelle probability cascade calculus including Bolthausen-Sznitman invariance
Used in Appendix A and Section 6.2 to evaluate the cavity lower-bound functionals.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Overlap Gap Property in Principal Submatrix Recovery." pith.science (2026). https://pith.science/paper/WKDOXQ3X

@misc{pith2026190809959,
  author       = {Pith},
  title        = {Pith review of: The Overlap Gap Property in Principal Submatrix Recovery},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WKDOXQ3X}},
  note         = {Machine review of arXiv:1908.09959}
}

abstract

We study support recovery for a $k \times k$ principal submatrix with elevated mean $\lambda/N$, hidden in an $N\times N$ symmetric mean zero Gaussian matrix. Here $\lambda>0$ is a universal constant, and we assume $k = N \rho$ for some constant $\rho \in (0,1)$. We establish that {there exists a constant $C>0$ such that} the MLE recovers a constant proportion of the hidden submatrix if $\lambda {\geq C} \sqrt{\frac{1}{\rho} \log \frac{1}{\rho}}$, {while such recovery is information theoretically impossible if $\lambda = o( \sqrt{\frac{1}{\rho} \log \frac{1}{\rho}} )$}. The MLE is computationally intractable in general, and in fact, for $\rho>0$ sufficiently small, this problem is conjectured to exhibit a \emph{statistical-computational gap}. To provide rigorous evidence for this, we study the likelihood landscape for this problem, and establish that for some $\varepsilon>0$ and $\sqrt{\frac{1}{\rho} \log \frac{1}{\rho} } \ll \lambda \ll \frac{1}{\rho^{1/2 + \varepsilon}}$, the problem exhibits a variant of the \emph{Overlap-Gap-Property (OGP)}. As a direct consequence, we establish that a family of local MCMC based algorithms do not achieve optimal recovery. Finally, we establish that for $\lambda > 1/\rho$, a simple spectral method recovers a constant proportion of the hidden submatrix.

Figures

Figures reproduced from arXiv: 1908.09959 by the authors.

**Figure 1.** An illustration of OGP. Observe that under the conditions of Definition 1.3, there exists a certain threshold energy Ethreshold such that the set of possible overlaps { 1 N (x, v) : x ∈ ΣN (ρ),(x, Ax) > NEthreshold} has a gap. Our first result is information theoretic, and derives the minimum signal strength λ required for approximate support recovery Theorem 1.2. If λ = o q1 ρ log 1 ρ , approximate recovery is i… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

81 extracted references · 67 canonical work pages

[50]

On the unbalanced cut problem and the generalized sherrington- kirkpatrick model

Aukosh Jagannath and Subhabrata Sen. On the unbalanced cut problem and the generalized sherrington- kirkpatrick model. Ann. Inst. Henri Poincar. D , to appear

work page
[1]

Community detection and stochastic block models: recent developments

Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446–6531, 2017

2017
[2]

On the solution-space geometry of ran- dom constraint satisfaction problems

Dimitris Achlioptas, Amin Coja-Oghlan, and Federico Ricci-Tersenghi. On the solution-space geometry of ran- dom constraint satisfaction problems. Random Structures & Algorithms , 38(3):251–268, 2011

work page 2011
[3]

The algorithmic hardness threshold for continuous random energy models

Louigi Addario-Berry and Pascal Maillard. The algorithmic hardness threshold for continuous random energy models. arXiv preprint arXiv:1810.05129 , 2018

arXiv 2018
[4]

Extended variational principle for the sherrington- kirkpatrick spin-glass model

Michael Aizenman, Robert Sims, and Shannon L Starr. Extended variational principle for the sherrington- kirkpatrick spin-glass model. Physical Review B, 68(21):214403, 2003

work page 2003
[5]

Finding a large hidden clique in a random graph

Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4):457–466, 1998

work page 1998
[6]

High-dimensional analysis of semideﬁnite relaxations for sparse prin- cipal components

Arash A Amini and Martin J Wainwright. High-dimensional analysis of semideﬁnite relaxations for sparse prin- cipal components. In 2008 IEEE International Symposium on Information Theory , pages 2454–2458. IEEE, 2008

work page 2008
[7]

Spin glass computations and Ruelle’s probability cascades

Louis-Pierre Arguin. Spin glass computations and Ruelle’s probability cascades. J. Stat. Phys., 126(4-5):951–976, 2007

work page 2007

Show all 81 references

[8]

Free energy wells and overlap gap property in sparse pca

G´ erard Ben Arous, Alexander S Wein, and Ilias Zadik. Free energy wells and overlap gap property in sparse pca. In Conference on Learning Theory, pages 479–482. PMLR, 2020

2020
[9]

Parisi formula for the ground state energy in the mixed p-spin model

Antonio Auﬃnger and Wei-Kuo Chen. Parisi formula for the ground state energy in the mixed p-spin model. The Annals of Probability , 45(6B):4617–4631, Nov 2017

2017
[10]

The sk model is full-step replica symmetry breaking at zero temperature

Antonio Auﬃnger, Wei-Kuo Chen, and Qiang Zeng. The sk model is full-step replica symmetry breaking at zero temperature. arXiv preprint arXiv:1703.06872 , 2017

2017 arXiv
[11]

Some exact results on the ultrametric overlap distribution in mean ﬁeld spin glass models (i)

Francesco Baﬃoni and Francesco Rosati. Some exact results on the ultrametric overlap distribution in mean ﬁeld spin glass models (i). The European Physical Journal B-Condensed Matter and Complex Systems , 17(3):439–447, 2000

2000
[12]

Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices

Jinho Baik, G´ erard Ben Arous, Sandrine P´ ech´ e, et al. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. The Annals of Probability , 33(5):1643–1697, 2005

2005
[13]

Statistical and computational tradeoﬀs in biclustering

Sivaraman Balakrishnan, Mladen Kolar, Alessandro Rinaldo, Aarti Singh, and Larry Wasserman. Statistical and computational tradeoﬀs in biclustering. In NeurIPS 2011 workshop on computational trade-oﬀs in statistical learning, volume 4, 2011

2011
[14]

A nearly tight sum-of-squares lower bound for the planted clique problem

Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM Journal on Computing , 48(2):687–735, 2019

2019
[15]

All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation

Jean Barbier, Nicolas Macris, and Cynthia Rush. All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation. arXiv preprint arXiv:2006.07971 , 2020

2006 arXiv
[16]

Equilibrium statistical mechanics of bipartite spin systems

Adriano Barra, Giuseppe Genovese, and Francesco Guerra. Equilibrium statistical mechanics of bipartite spin systems. Journal of Physics A: Mathematical and Theoretical , 44(24):245002, 2011. 39

2011
[17]

Algorithmic thresholds for tensor pca.arXiv preprint arXiv:1808.00921, 2018

G´ erard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Algorithmic thresholds for tensor pca.arXiv preprint arXiv:1808.00921, 2018

2018 arXiv
[18]

Spectral gap estimates in mean ﬁeld spin glasses

G´ erard Ben Arous and Aukosh Jagannath. Spectral gap estimates in mean ﬁeld spin glasses. Communications in Mathematical Physics , 361(1):1–52, 2018

2018
[19]

The eigenvalues and eigenvectors of ﬁnite, low rank pertur- bations of large random matrices

Florent Benaych-Georges and Raj Rao Nadakuditi. The eigenvalues and eigenvectors of ﬁnite, low rank pertur- bations of large random matrices. Advances in Mathematics, 227(1):494–521, 2011

2011
[20]

Complexity theoretic lower bounds for sparse principal component de- tection

Quentin Berthet and Philippe Rigollet. Complexity theoretic lower bounds for sparse principal component de- tection. In Conference on Learning Theory, pages 1046–1066, 2013

2013
[21]

Energy landscape for large average submatrix detection problems in gaussian random matrices

Shankar Bhamidi, Partha S Dey, and Andrew B Nobel. Energy landscape for large average submatrix detection problems in gaussian random matrices. Probability Theory and Related Fields , 168(3-4):919–983, 2017

2017
[22]

Oxford university press, 2013

St´ ephane Boucheron, G´ abor Lugosi, and Pascal Massart.Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013

2013
[23]

Reducibility and computational lower bounds for problems with planted sparse structure

Matthew Brennan, Guy Bresler, and Wasim Huleihel. Reducibility and computational lower bounds for problems with planted sparse structure. arXiv preprint arXiv:1806.07508 , 2018

2018 arXiv
[24]

Universality of computational lower bounds for submatrix detection

Matthew Brennan, Guy Bresler, and Wasim Huleihel. Universality of computational lower bounds for submatrix detection. arXiv preprint arXiv:1902.06916 , 2019

1902 arXiv
[25]

Detection of a sparse submatrix of a high-dimensional noisy matrix

Cristina Butucea, Yuri I Ingster, et al. Detection of a sparse submatrix of a high-dimensional noisy matrix. Bernoulli, 19(5B):2652–2688, 2013

2013
[26]

Sharp variable selection of a sparse submatrix in a high- dimensional noisy matrix

Cristina Butucea, Yuri I Ingster, and Irina A Suslina. Sharp variable selection of a sparse submatrix in a high- dimensional noisy matrix. ESAIM: Probability and Statistics , 19:115–134, 2015

2015
[27]

Computational and statistical boundaries for submatrix localization in a large noisy matrix

T Tony Cai, Tengyuan Liang, Alexander Rakhlin, et al. Computational and statistical boundaries for submatrix localization in a large noisy matrix. The Annals of Statistics , 45(4):1403–1430, 2017

2017
[28]

Computational and statistical tradeoﬀs via convex relaxation

Venkat Chandrasekaran and Michael I Jordan. Computational and statistical tradeoﬀs via convex relaxation. Proceedings of the National Academy of Sciences , 110(13):E1181–E1190, 2013

2013
[29]

Suboptimality of local algorithms for a class of max-cut problems

Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, Mustazee Rahman, et al. Suboptimality of local algorithms for a class of max-cut problems. The Annals of Probability , 47(3):1587–1618, 2019

2019
[30]

Statistical-computational tradeoﬀs in planted problems and submatrix localiza- tion with a growing number of clusters and submatrices

Yudong Chen and Jiaming Xu. Statistical-computational tradeoﬀs in planted problems and submatrix localiza- tion with a growing number of clusters and submatrices. The Journal of Machine Learning Research , 17(1):882– 938, 2016

2016
[31]

Walksat stalls well below satisﬁability

Amin Coja-Oghlan, Amir Haqshenas, and Samuel Hetterich. Walksat stalls well below satisﬁability. SIAM Jour- nal on Discrete Mathematics , 31(2):1160–1173, 2017

2017
[32]

Elements of information theory john wiley & sons

Thomas M Cover and Joy A Thomas. Elements of information theory john wiley & sons. New York, 68:69–73, 1991

1991
[33]

N. G. de Bruijn and P. Erd¨ os. Some linear and some quadratic recursion formulas. II. Nederl. Akad. Wetensch. Proc. Ser. A. 55 = Indagationes Math. , 14:152–163, 1952

1952
[34]

Information-theoretically optimal sparse pca

Yash Deshpande and Andrea Montanari. Information-theoretically optimal sparse pca. In 2014 IEEE Interna- tional Symposium on Information Theory , pages 2197–2201. IEEE, 2014

2014
[35]

Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems

Yash Deshpande and Andrea Montanari. Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems. In Conference on Learning Theory, pages 523–562, 2015

2015
[36]

Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula

Mohamad Dia, Nicolas Macris, Florent Krzakala, Thibault Lesieur, Lenka Zdeborov´ a, et al. Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula. In Advances in Neural Information Processing Systems, pages 424–432, 2016

2016
[37]

Subexponential-time algorithms for sparse pca

Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Subexponential-time algorithms for sparse pca. arXiv preprint arXiv:1907.11635 , 2019

1907 arXiv
[38]

Statistical algorithms and a lower bound for detecting planted cliques

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM) , 64(2):8, 2017

2017
[39]

Finding a large submatrix of a gaussian random matrix

David Gamarnik and Quan Li. Finding a large submatrix of a gaussian random matrix. The Annals of Statistics , 46(6A):2511–2561, 2018

2018
[40]

Performance of sequential local algorithms for the random nae-k-sat prob- lem

David Gamarnik and Madhu Sudan. Performance of sequential local algorithms for the random nae-k-sat prob- lem. SIAM Journal on Computing , 46(2):590–619, 2017

2017
[41]

High dimensional regression with binary coeﬃcients

David Gamarnik and Ilias Zadik. High dimensional regression with binary coeﬃcients. estimating squared error and a phase transtition. In Conference on Learning Theory, pages 948–953, 2017

2017
[42]

Sparse high-dimensional linear regression

David Gamarnik and Ilias Zadik. Sparse high-dimensional linear regression. algorithmic barriers and a local search algorithm. arXiv preprint arXiv:1711.04952 , 2017

2017 arXiv
[43]

The landscape of the planted clique problem: Dense subgraphs and the overlap gap property

David Gamarnik and Ilias Zadik. The landscape of the planted clique problem: Dense subgraphs and the overlap gap property. arXiv preprint arXiv:1904.07174 , 2019

1904 arXiv
[44]

Sparse cca: Adaptive estimation and computational barriers

Chao Gao, Zongming Ma, Harrison H Zhou, et al. Sparse cca: Adaptive estimation and computational barriers. The Annals of Statistics , 45(5):2074–2101, 2017. 40

2017
[45]

On the integrality gap of degree-4 sum of squares for planted clique

Samuel B Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, and Tselil Schramm. On the integrality gap of degree-4 sum of squares for planted clique. ACM Transactions on Algorithms (TALG) , 14(3):28, 2018

2018
[46]

Fast spectral algorithms from sum-of- squares proofs: tensor decomposition and planted sparse vectors

Samuel B Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer. Fast spectral algorithms from sum-of- squares proofs: tensor decomposition and planted sparse vectors. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages 178–191. ACM, 2016

2016
[47]

Approximate ultrametricity for random measures and applications to spin glasses

Aukosh Jagannath. Approximate ultrametricity for random measures and applications to spin glasses. Comm. Pure Appl. Math. , 70(4):611–664, 2017

2017
[48]

Max κ-cut and the inhomogeneous potts spin glass

Aukosh Jagannath, Justin Ko, and Subhabrata Sen. Max κ-cut and the inhomogeneous potts spin glass. The Annals of Applied Probability , 28(3):1536–1572, 2018

2018
[49]

Statistical thresholds for tensor PCA.Ann

Aukosh Jagannath, Patrick Lopatto, and L´ eo Miolane. Statistical thresholds for tensor PCA.Ann. Appl. Probab., 30(4):1910–1933, 2020

1910
[51]

A dynamic programming approach to the parisi functional

Aukosh Jagannath and Ian Tobasco. A dynamic programming approach to the parisi functional. Proceedings of the American Mathematical Society , 144(7):3135–3150, 2016

2016
[52]

Low temperature asymptotics of spherical mean ﬁeld spin glasses

Aukosh Jagannath and Ian Tobasco. Low temperature asymptotics of spherical mean ﬁeld spin glasses. Commu- nications in Mathematical Physics , 352(3):979–1017, 2017

2017
[53]

Some properties of the phase diagram for mixed p-spin glasses

Aukosh Jagannath and Ian Tobasco. Some properties of the phase diagram for mixed p-spin glasses. Probability Theory and Related Fields , 167(3-4):615–672, 2017

2017
[54]

Minimax localization of structural information in large noisy matrices

Mladen Kolar, Sivaraman Balakrishnan, Alessandro Rinaldo, and Aarti Singh. Minimax localization of structural information in large noisy matrices. In Advances in Neural Information Processing Systems, pages 909–917, 2011

2011
[55]

Mutual information in rank-one matrix estimation

Florent Krzakala, Jiaming Xu, and Lenka Zdeborov´ a. Mutual information in rank-one matrix estimation. In 2016 IEEE Information Theory Workshop (ITW) , pages 71–75. IEEE, 2016

2016
[56]

Fundamental limits of symmetric low-rank matrix estimation.Probability Theory and Related Fields, 173(3-4):859–929, 2019

Marc Lelarge and L´ eo Miolane. Fundamental limits of symmetric low-rank matrix estimation.Probability Theory and Related Fields, 173(3-4):859–929, 2019

2019
[57]

Phase transitions in sparse pca

Thibault Lesieur, Florent Krzakala, and Lenka Zdeborov´ a. Phase transitions in sparse pca. In2015 IEEE Inter- national Symposium on Information Theory (ISIT) , pages 1635–1639. IEEE, 2015

2015
[58]

Thibault Lesieur, Florent Krzakala, and Lenka Zdeborov´ a. Constrained low-rank matrix estimation: Phase tran- sitions, approximate message passing and applications.Journal of Statistical Mechanics: Theory and Experiment, 2017(7):073403, 2017

2017
[59]

Sum-of-squares lower bounds for sparse pca

Tengyu Ma and Avi Wigderson. Sum-of-squares lower bounds for sparse pca. In Advances in Neural Information Processing Systems, pages 1612–1620, 2015

2015
[60]

Computational barriers in minimax submatrix detection.The Annals of Statistics, 43(3):1089–1116, 2015

Zongming Ma and Yihong Wu. Computational barriers in minimax submatrix detection.The Annals of Statistics, 43(3):1089–1116, 2015

2015
[61]

Sum-of-squares lower bounds for planted clique

Raghu Meka, Aaron Potechin, and Avi Wigderson. Sum-of-squares lower bounds for planted clique. InProceedings of the forty-seventh annual ACM symposium on Theory of computing , pages 87–96. ACM, 2015

2015
[62]

Clustering of solutions in the random satisﬁability problem

Marc M´ ezard, Thierry Mora, and Riccardo Zecchina. Clustering of solutions in the random satisﬁability problem. Physical Review Letters, 94(19):197205, 2005

2005
[63]

Finding one community in a sparse graph

Andrea Montanari. Finding one community in a sparse graph. Journal of Statistical Physics , 161(2):273–299, 2015

2015
[64]

Optimization of the sherrington-kirkpatrick hamiltonian

Andrea Montanari. Optimization of the sherrington-kirkpatrick hamiltonian. arXiv preprint arXiv:1812.10897 , 2018

2018 arXiv
[65]

On the limitation of spectral methods: From the gaussian hidden clique problem to rank-one perturbations of gaussian tensors

Andrea Montanari, Daniel Reichman, and Ofer Zeitouni. On the limitation of spectral methods: From the gaussian hidden clique problem to rank-one perturbations of gaussian tensors. InAdvances in Neural Information Processing Systems, pages 217–225, 2015

2015
[66]

The computer science and physics of community detection: Landscapes, phase transitions, and hardness

Cristopher Moore. The computer science and physics of community detection: Landscapes, phase transitions, and hardness. arXiv preprint arXiv:1702.00467 , 2017

2017 arXiv
[67]

The Parisi ultrametricity conjecture

Dmitry Panchenko. The Parisi ultrametricity conjecture. Ann. of Math. (2) , 177(1):383–393, 2013

2013
[68]

The Sherrington-Kirkpatrick model

Dmitry Panchenko. The Sherrington-Kirkpatrick model. Springer, 2013

2013
[69]

The Parisi formula for mixed p-spin models

Dmitry Panchenko. The Parisi formula for mixed p-spin models. Ann. Probab., 42(3):946–958, 2014

2014
[70]

The free energy in a multi-species Sherrington-Kirkpatrick model

Dmitry Panchenko. The free energy in a multi-species Sherrington-Kirkpatrick model. Ann. Probab., 43(6):3494– 3513, 2015

2015
[71]

Free energy in the mixed p-spin models with vector spins

Dmitry Panchenko. Free energy in the mixed p-spin models with vector spins. The Annals of Probability , 46(2):865–896, 2018

2018
[72]

Free energy in the potts spin glass

Dmitry Panchenko. Free energy in the potts spin glass. The Annals of Probability , 46(2):829–864, 2018

2018
[73]

Local algorithms for independent sets are half-optimal

Mustazee Rahman, Balint Virag, et al. Local algorithms for independent sets are half-optimal. The Annals of Probability, 45(3):1543–1577, 2017. 41

2017
[74]

A statistical model for tensor pca

Emile Richard and Andrea Montanari. A statistical model for tensor pca. In Advances in Neural Information Processing Systems, pages 2897–2905, 2014

2014
[75]

Average-case complexity of detecting cliques

Benjamin Rossman. Average-case complexity of detecting cliques . PhD thesis, Massachusetts Institute of Tech- nology, 2010

2010
[76]

Finding large average subma- trices in high dimensional data

Andrey A Shabalin, Victor J Weigman, Charles M Perou, Andrew B Nobel, et al. Finding large average subma- trices in high dimensional data. The Annals of Applied Statistics , 3(3):985–1012, 2009

2009
[77]

Michael Steele

J. Michael Steele. Probability theory and combinatorial optimization, volume 69 of CBMS-NSF Regional Confer- ence Series in Applied Mathematics . Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997

1997
[78]

Stroock and S

Daniel W. Stroock and S. R. Srinivasa Varadhan. Multidimensional diﬀusion processes. Classics in Mathematics. Springer-Verlag, Berlin, 2006. Reprint of the 1997 edition

2006
[79]

Following the ground-states of full-rsb spherical spin glasses

Eliran Subag. Following the ground-states of full-rsb spherical spin glasses. arXiv preprint arXiv:1812.04588 , 2018

2018 arXiv
[80]

Mean ﬁeld models for spin glasses

Michel Talagrand. Mean ﬁeld models for spin glasses. Volume II , volume 55 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics]...

2011
[81]

The kikuchi hierarchy and tensor pca

Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore. The kikuchi hierarchy and tensor pca. arXiv preprint arXiv:1904.03858, 2019. Sloan School of Management, Massachusetts Institute of Technology, gamarnik@mit.edu Department of Statistics and Actuarial Sciences and Departm...

1904 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [50]

On the unbalanced cut problem and the generalized sherrington- kirkpatrick model

Aukosh Jagannath and Subhabrata Sen. On the unbalanced cut problem and the generalized sherrington- kirkpatrick model. Ann. Inst. Henri Poincar. D , to appear

work page

[2] [1]

Community detection and stochastic block models: recent developments

Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446–6531, 2017

2017

[3] [2]

On the solution-space geometry of ran- dom constraint satisfaction problems

Dimitris Achlioptas, Amin Coja-Oghlan, and Federico Ricci-Tersenghi. On the solution-space geometry of ran- dom constraint satisfaction problems. Random Structures & Algorithms , 38(3):251–268, 2011

work page 2011

[4] [3]

The algorithmic hardness threshold for continuous random energy models

Louigi Addario-Berry and Pascal Maillard. The algorithmic hardness threshold for continuous random energy models. arXiv preprint arXiv:1810.05129 , 2018

arXiv 2018

[5] [4]

Extended variational principle for the sherrington- kirkpatrick spin-glass model

Michael Aizenman, Robert Sims, and Shannon L Starr. Extended variational principle for the sherrington- kirkpatrick spin-glass model. Physical Review B, 68(21):214403, 2003

work page 2003

[6] [5]

Finding a large hidden clique in a random graph

Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4):457–466, 1998

work page 1998

[7] [6]

High-dimensional analysis of semideﬁnite relaxations for sparse prin- cipal components

Arash A Amini and Martin J Wainwright. High-dimensional analysis of semideﬁnite relaxations for sparse prin- cipal components. In 2008 IEEE International Symposium on Information Theory , pages 2454–2458. IEEE, 2008

work page 2008

[8] [7]

Spin glass computations and Ruelle’s probability cascades

Louis-Pierre Arguin. Spin glass computations and Ruelle’s probability cascades. J. Stat. Phys., 126(4-5):951–976, 2007

work page 2007