Pith. sign in

REVIEW 2 major objections 6 minor 261 references

Approximate stochastic localization yields a weak Poincaré inequality for the SK Gibbs measure at β < 1/2, so Glauber dynamics samples from a warm start.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-10 12:06 UTC pith:BAEC7FD5

load-bearing objection Clean transfer theorem that turns the authors' prior ASL estimates into a WPI for SK at β<1/2 and a simpler Glauber sampler; the novelty is real, the dependence on [DLSS26] is explicit and non-circular. the 2 major comments →

arxiv 2607.08160 v1 pith:BAEC7FD5 submitted 2026-07-09 math.PR math-phmath.FAmath.MP

Weak Poincar\'e Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick Model

Ewan Davies , Holden Lee , Juspreet Singh Sandhu , Jonathan Shi This is my paper
classification math.PR math-phmath.FAmath.MP MSC 60J6082B4468W20
keywords weak Poincaré inequalitystochastic localizationSherrington–Kirkpatrick modelGlauber dynamicswarm startproximal samplerconductanceJarzynski equality
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper shows that a weak Poincaré inequality for a target measure can be proved by first establishing it for a regular approximate stochastic localization process and then transferring the inequality through conductance and Gaussian smoothing. Applied to the Sherrington–Kirkpatrick spin-glass measure, the method gives a weak Poincaré inequality for every inverse temperature β less than 1/2. The inequality is strong enough that ordinary Glauber dynamics, once given a warm start produced by a short Langevin or approximate-localization run, mixes to total-variation accuracy ε in time that is polynomial in dimension times a factor exponential only in 1/ε. The result therefore replaces a more elaborate sampling algorithm with a structurally simpler two-phase procedure and supplies a concrete functional-inequality step toward the long-standing conjecture that Glauber dynamics mixes throughout the replica-symmetric regime.

Core claim

Under three natural regularity assumptions on an approximate stochastic localization process (bounded magnetization error, Lipschitz approximate drift, and a local weak Poincaré inequality), the target measure itself satisfies a weak Poincaré inequality whose constants depend only on those assumptions. Specializing to the SK model at β < 1/2, where the assumptions are already known to hold, yields a (n^{-1} exp(−C/ε), ε)-weak Poincaré inequality with high probability over the disorder.

What carries the argument

The decomposition theorem for the weak Poincaré inequality: a WPI for the localized measures together with a WPI for the proximal sampler (itself obtained by s-conductance of the Gaussian-noised localization law) imply a WPI for the original measure via a joint Dirichlet-form argument.

Load-bearing premise

The second-moment control on the difference between true and approximate magnetizations, together with uniform Lipschitzness of the approximate magnetization, must hold; both are presently available only up to β = 1/2.

What would settle it

If, for some β0 < 1/2 and a sequence of GOE matrices, either the magnetization-error integral or the approximate-magnetization Lipschitz constant grows with n, then the claimed weak Poincaré constant for the SK measure would fail to be of the stated form.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Glauber dynamics started from a single warm sample mixes to total-variation distance ε in O(n exp(O(1/ε))) steps for every β < 1/2.
  • The same scaffolding strategy can be reused for any measure that admits an approximate localization process with second-moment drift control and local functional inequalities.
  • A natural annealed TAP distribution is a polynomial-warm start for the localization law, so Langevin dynamics on the annealed free energy produces the required warm start in poly(n) time.
  • The quantitative WPI is still too weak for plain simulated annealing, so stronger second-moment or operator-norm assumptions would be needed to reach the full replica-symmetric window by the same route.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the second-moment magnetization bounds can be extended past β = 1/2, the same argument would immediately give a weak Poincaré inequality deeper into the replica-symmetric regime.
  • The conductance-transfer idea may apply to other discrete spin systems where only approximate, not exact, localization is presently under control.
  • Because the warm-start phase is independent of the final accuracy ε, the method separates “finding a good region” from “mixing inside that region,” a separation that could simplify other high-temperature sampling proofs.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 6 minor

Summary. The paper develops a transfer method for weak Poincaré inequalities (WPIs): under magnetization-error, Lipschitz-ASL-drift, and local-WPI assumptions (Assumptions 1.1–1.3), a WPI for the target measure μ is obtained by scaffolding the SL law p_T0 with an approximate SL process, proving s-conductance via small-distance couplings and Gaussian isoperimetry (Theorem 4.4), transferring to the proximal sampler (Lemma 4.5), and combining with a Gibbs-decomposition theorem (Theorem 3.1 / Corollary 3.2). Specializing to the SK model at β < 1/2 (via estimates imported from the authors’ prior work [DLSS26]) yields a (n^{-1} e^{-C/ε}, ε)-WPI with high probability (Corollary 1.5). The remaining sections establish a path-space LSI for annealed (Jarzynski/TAP) measures (Theorems 6.7–6.11), show that these measures are warm starts for the SL law (Theorem 7.2), and conclude that Glauber dynamics from a Langevin warm start samples the SK Gibbs measure in time n exp(O(1/ε)^{O(1)}) (Theorem 1.6 / Algorithm 1).

Significance. If the imported regularity estimates hold, the work supplies a clean structural reduction from ASL-type second-moment/Lipschitz control to a WPI, and thereby to a substantially simpler sampling algorithm (warm-start Glauber) than the full ASL+Jarzynski+polarized-walk pipeline of [DLSS26]. This is a genuine conceptual advance for spin-glass sampling and for the broader program of obtaining functional inequalities under conditions weaker than those required by classical stochastic localization. The path-space LSI for Cameron–Martin Lipschitz tilts (Theorem 6.7) and the warm-start scaffolding (§7) are of independent interest. The quantitative WPI is too weak for simulated annealing, so the result is a structural rather than quantitative resolution of the replica-symmetric mixing conjecture; that limitation is stated clearly by the authors.

major comments (2)
  1. The load-bearing analytic inputs—Assumption 1.1 (second-moment magnetization error), Assumption 1.2 (uniform Lipschitzness of the approximate magnetization), and the local WPI of Assumption 1.3—are taken wholesale from the authors’ prior paper [DLSS26] and are known only for β < 1/2. Within the present manuscript the transfer argument itself is self-contained, but the SK specialization (Corollary 1.5 and Theorem 1.6) stands or falls exactly with those external estimates. The paper should state this dependence more prominently in the introduction and in the statement of Corollary 1.5 (e.g., “conditional on the high-probability event of [DLSS26, Theorems X–Y]”), so that the logical scope of the new contribution is unambiguous.
  2. Theorem 1.4 produces a WPI whose Poincaré constant is exp(−O(1/ε)). As the authors note (§1.2), this is already trivial for ε = O(1/n) and is far weaker than the (n^{−O(1)}, o(n^{−1}))-WPI that would permit simulated annealing. The algorithmic claim (Theorem 1.6) therefore relies on a separate warm-start construction whose runtime still carries an exp((1/ε)^{O(1)}) factor. The manuscript would be strengthened by a short quantitative comparison (perhaps a table or a paragraph in §1.2) of the resulting end-to-end complexity against [DLSS26] and against the spherical p-spin results of [HMRW25], so that the reader can assess how much is gained by the simpler algorithm versus how much is lost in the ε-dependence.
minor comments (6)
  1. Figure 1.1 is helpful but the caption and the surrounding text in §1.4 could more explicitly label which sets are A♯/B♯ and which coupling is being drawn; a reader encountering the figure before §4 may not immediately see the correspondence.
  2. Notation for the approximate process switches between ŷ_t / m̂ and y_t / m̂ in different sections; a single consistent convention (perhaps always m̂, ŷ) would reduce cognitive load.
  3. In the proof of Theorem 4.4, Case 2, the constant 4 appearing in the definition of ŝ = (s/4) exp(−4(E_{T1}+1)/s) is chosen for convenience; a parenthetical remark that any fixed multiple works (with adjusted O(·) constants) would clarify that the argument is robust.
  4. Lemma 4.6 is elementary but useful; a one-line reference to the standard “I−P ≽ (1/2)(I−P^{2})” spectral identity (or an explicit citation) would help readers who have not seen the continuous-time reduction before.
  5. Several absolute constants (C in Theorem 6.7, the O(·) factors in the warm-start exponents of Theorem 7.2) are left unspecified. For a pure existence result this is fine, but a remark that they are universal (independent of n, β, T) would be reassuring.
  6. Typographical: “Jarzysnki” appears once in §7; “Lipscshitz” once in §6.3; “functinoal” in Appendix A. Standard copy-editing will catch these.

Circularity Check

1 steps flagged

Sequential self-citation of [DLSS26] supplies the load-bearing Assumptions 1.1–1.3, but the transfer theorems themselves are independent and non-circular.

specific steps
  1. self citation load bearing [Abstract; §1.1 Assumptions 1.1–1.3; proof of Corollary 1.5]
    "A prior result of the authors [arXiv:2605.03718, 2026] proves the ASL process for the Sherrington–Kirkpatrick model satisfies the required regularity conditions. … We work on an event of probability at least 1-δ … on which … Assumption 1.1 and Assumption 1.2 hold by [DLSS26]; and, by Theorem 5.1 with T0 large enough, Assumption 1.3 holds …"

    The three analytic hypotheses that make Theorem 1.4 non-vacuous for the SK model (magnetization error, Lipschitz ASL drift, and local WPI) are supplied exclusively by the authors’ own prior paper. The present work does not re-derive them; it only transfers them into a WPI. This is load-bearing self-citation, but not a definitional loop: the transfer argument itself is independent of how the assumptions were obtained.

full rationale

The paper’s central claim (Theorem 1.4) is an implication: under Assumptions 1.1–1.3 the target measure satisfies a weak Poincaré inequality. Those assumptions are imported from the authors’ prior work [DLSS26] (explicitly stated in the abstract, §1.1, and the proof of Corollary 1.5). That is ordinary sequential dependence, not circular definition: the present manuscript treats the magnetization-error, Lipschitz-drift, and local-WPI estimates as black-box hypotheses and derives new functional inequalities (decomposition Theorem 3.1, s-conductance of p_T0 via the ASL scaffold in Theorem 4.4, proximal-sampler WPI in Lemma 4.5, path-space LSI in Theorem 6.7, warm-start scaffolding in §7). No free parameter is fitted to data and then re-presented as a prediction; no uniqueness theorem is invoked to forbid alternatives; no ansatz is smuggled in via citation. The algorithmic consequence (Theorem 1.6) likewise rests only on the same stated hypotheses plus standard discretization and mixing lemmas. Consequently the derivation is self-contained once the imported estimates are granted, and the circularity score is low.

Axiom & Free-Parameter Ledger

3 free parameters · 6 axioms · 2 invented entities

The central claims rest on three domain assumptions imported from prior ASL analysis of SK, standard functional-inequality and Gaussian-isoperimetry tools, and the restriction β < 1/2. No new physical entities are postulated; free parameters are only the usual temperature cut-off, localization times, and accuracy ε that appear explicitly in the statements.

free parameters (3)
  • localization times T0 < T1
    Chosen large enough constants depending on β so that local concentration and ASL regularity hold; appear in Assumptions 1.1–1.3 and Theorem 1.4.
  • accuracy parameter ε in the WPI
    Free trade-off between Poincaré constant e^{-O(1/ε)} and error term; user-chosen, not fitted to data.
  • failure probability δ and constants C(β,δ)
    High-probability constants over GOE disorder; depend on β and δ but are not numerically fitted.
axioms (6)
  • domain assumption Assumption 1.1: second-moment magnetization error E∥m(yt)−m̂(yt)∥² ≤ ε(t)² on [0,T1]
    Taken from [DLSS26]; supplies the KL bound between ideal and approximate SL laws (Lemma 2.11).
  • domain assumption Assumption 1.2: approximate magnetization m̂ is L-Lipschitz
    Gives log-Sobolev for the ASL law (Lemma 2.12) and Cameron–Martin Lipschitz constants for path-space arguments.
  • domain assumption Assumption 1.3: with high probability the time-T0 localized measure satisfies a local WPI
    Proved for SK in §5 by needle decomposition and covariance bounds; required for the global decomposition (Corollary 3.2).
  • domain assumption β < 1/2 for the SK model
    Regime in which [DLSS26] establishes Assumptions 1.1–1.2; the paper does not claim results for 1/2 ≤ β < 1.
  • standard math Girsanov, Cheeger’s inequality for s-conductance, Gaussian isoperimetry, Gross LSI on Wiener space, Holley–Stroock perturbation
    Classical tools used throughout §§2–6; cited to standard references.
  • domain assumption Assumption 6.1: Jarzynski weights have Lipschitz drift (for warm-start construction)
    Needed only for the algorithmic warm-start (§§6–8), not for the pure WPI statement Theorem 1.4.
invented entities (2)
  • Approximate stochastic localization (ASL) scaffolding for WPI transfer independent evidence
    purpose: Regular proxy process whose LSI/conductance can be transferred to the ideal SL law
    Methodological construct, not a physical entity; independent evidence is the derived theorems themselves.
  • Annealed distributions ϱ_t defined via TAP free energy / Jarzynski reweighting independent evidence
    purpose: Explicit densities that approximate the SL law and serve as warm starts
    Already present in [DLSS26]; reused here for sampling. Falsifiable via the LSI and warm-start claims.

pith-pipeline@v1.1.0-grok45 · 64121 in / 3543 out tokens · 41003 ms · 2026-07-10T12:06:14.608529+00:00 · methodology

0 comments
read the original abstract

We develop a new method for proving a weak functional inequality by first proving it for a sufficiently regular sequence of distributions approximating the stochastic localization (SL) process, and then transferring it to the desired distribution via regularity of the SL process and conductance arguments. We use this strategy to prove a weak Poincar\'e inequality (WPI) holds for the Gibbs measure of the Sherrington-Kirkpatrick model when $\beta < \frac{1}{2}$. A prior result of the authors [arXiv:2605.03718, 2026] proves the ASL process for the Sherrington-Kirkpatrick model satisfies the required regularity conditions. A consequence of the WPI is that a much simpler algorithm -- Glauber dynamics with a warm-start -- efficiently samples the Gibbs measure of the SK model at $\beta < \frac{1}{2}$. This is a significant structural step towards resolution of the conjecture that Glauber dynamics mixes fast in the replica-symmetric regime for the Sherrington-Kirkpatrick model [arXiv:2504.20539, Open-Problem 15, 2025].

Figures

Figures reproduced from arXiv: 2607.08160 by Ewan Davies, Holden Lee, Jonathan Shi, Juspreet Singh Sandhu.

Figure 1
Figure 1. Figure 1 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 1.1
Figure 1.1. Figure 1.1: Proving a WPI for the SL distribution pT0 (orange, dashed) by “scaffolding” with the ASL process p̂T1 (blue, solid). Small drift error between p̂T1 and pT1 (red, solid) means that that they are close together, but the density of pT1 can still go to zero where p̂T1 is non-zero. Gaussian noise and the small-distance coupling (red line segment) lift the corresponding areas of pT0 away from zero. To apply th… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

261 extracted references · 261 canonical work pages · 55 internal anchors

  1. [1]

    Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2

    Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta< 1/2 , author=. arXiv preprint arXiv:2605.03718 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  2. [2]

    Sampling, Diffusions, and Stochastic Localization

    Montanari, Andrea , year = 2023, month = may, number =. Sampling,. doi:10.48550/arXiv.2305.10690 , archiveprefix =. 2305.10690 , primaryclass =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2305.10690 2023

  3. [3]

    , year = 1997, month = apr, journal =

    Jarzynski, C. , year = 1997, month = apr, journal =. Nonequilibrium

    work page 1997

  4. [4]

    Probability Theory and Related Fields , volume =

    Taming Correlations through Entropy-Efficient Measure Decompositions with Applications to Mean-Field Approximation , author =. Probability Theory and Related Fields , volume =. doi:10.1007/s00440-019-00924-2 , langid =

    work page doi:10.1007/s00440-019-00924-2

  5. [5]

    Dynamical

    Adhikari, Arka and Brennecke, Christian and. Dynamical. 2021 , journal =. doi:10.1007/s10955-021-02773-7 , langid =

    work page doi:10.1007/s10955-021-02773-7 2021

  6. [6]

    The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case

    The quantum approximate optimization algorithm needs to see the whole graph: a typical case , author=. arXiv preprint arXiv:2004.09002 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  7. [7]

    The Annals of Statistics , volume=

    Approximate message passing algorithms for rotationally invariant matrices , author=. The Annals of Statistics , volume=. 2022 , publisher=

    work page 2022

  8. [8]

    Information and Inference: A Journal of the IMA , volume=

    State evolution for general approximate message passing algorithms, with applications to spatial coupling , author=. Information and Inference: A Journal of the IMA , volume=. 2013 , publisher=

    work page 2013

  9. [9]

    preprint , year=

    Operator-valued non-commutative probability , author=. preprint , year=

    work page

  10. [10]

    International Conference on Artificial Intelligence and Statistics , pages=

    Mirrorless mirror descent: A natural derivation of mirror descent , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2021 , organization=

    work page 2021

  11. [11]

    Free Probability Theory

    Free probability theory , author=. arXiv preprint arXiv:0911.0087 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  12. [12]

    Information and Inference: A Journal of the IMA , volume=

    State evolution for approximate message passing with non-separable functions , author=. Information and Inference: A Journal of the IMA , volume=. 2020 , publisher=

    work page 2020

  13. [13]

    2008 , publisher=

    Optimal transport: old and new , author=. 2008 , publisher=

    work page 2008

  14. [14]

    Princeton mathematical series , volume=

    Convex analysis , author=. Princeton mathematical series , volume=

    work page

  15. [15]

    MAXCUT QAOA performance guarantees for p >1

    Bounds on MAXCUT QAOA performance for p > 1 , author=. arXiv preprint arXiv:2010.11209 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  16. [16]

    Cimpri c

    J. Cimpri c. Real algebraic geometry for matrices over commutative rings. Journal of Algebra. 2012. doi:http://dx.doi.org/10.1016/j.jalgebra.2012.03.011

    work page doi:10.1016/j.jalgebra.2012.03.011 2012

  17. [17]

    A Quantum Approximate Optimization Algorithm

    A quantum approximate optimization algorithm , author=. arXiv preprint arXiv:1411.4028 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  18. [18]

    Training variational quantum algorithms is NP-hard

    Training variational quantum algorithms is NP-hard--even for logarithmically many qubits and free fermionic systems , author=. arXiv preprint arXiv:2101.07267 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  19. [19]

    Cycle lengths in expanding graphs

    Cycle lengths in expanding graphs , author=. arXiv preprint arXiv:1912.11011 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 1912

  20. [20]

    Discrete Mathematics , volume=

    On the second eigenvalue of a graph , author=. Discrete Mathematics , volume=. 1991 , publisher=

    work page 1991

  21. [21]

    2012 , publisher=

    Pseudorandomness , author=. 2012 , publisher=

    work page 2012

  22. [22]

    Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification

    Cut Sparsification of the Clique Beyond the Ramanujan Bound , author=. arXiv preprint arXiv:2008.05648 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  23. [23]

    Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Optimal lower bounds for sketching graph cuts , author=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

    work page 2019

  24. [24]

    Obstacles to State Preparation and Variational Optimization from Symmetry Protection

    Obstacles to state preparation and variational optimization from symmetry protection , author=. arXiv preprint arXiv:1910.08980 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 1910

  25. [25]

    The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples

    The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples , author=. arXiv preprint arXiv:2005.08747 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 2005

  26. [26]

    Hybrid quantum-classical algorithms for approximate graph coloring

    Hybrid quantum-classical algorithms for approximate graph coloring , author=. arXiv preprint arXiv:2011.13420 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  27. [27]

    Random Structures & Algorithms , volume=

    Almost all regular graphs are Hamiltonian , author=. Random Structures & Algorithms , volume=. 1994 , publisher=

    work page 1994

  28. [28]

    Random Structures & Algorithms , volume=

    On the max-cut of sparse random graphs , author=. Random Structures & Algorithms , volume=. 2018 , publisher=

    work page 2018

  29. [29]

    Cycle lengths in sparse random graphs

    Cycle lengths in sparse random graphs , author=. arXiv preprint arXiv:2008.13591 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  30. [30]

    the electronic journal of combinatorics , pages=

    Short cycles in random regular graphs , author=. the electronic journal of combinatorics , pages=

    work page

  31. [31]

    Graph theory and combinatorics (Cambridge, 1983), Academic Press, London , pages=

    Long cycles in sparse random graphs , author=. Graph theory and combinatorics (Cambridge, 1983), Academic Press, London , pages=

    work page 1983

  32. [32]

    Combinatorica , volume=

    Ramanujan graphs , author=. Combinatorica , volume=

    work page

  33. [33]

    Proceedings of the thirty-fifth annual ACM symposium on Theory of computing , pages=

    A proof of Alon's second eigenvalue conjecture , author=. Proceedings of the thirty-fifth annual ACM symposium on Theory of computing , pages=

    work page

  34. [34]

    The full replica symmetry breaking solution in mean-field spin glass models

    The full replica symmetry breaking solution in mean-field spin glass models , author=. arXiv preprint arXiv:1911.00557 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 1911

  35. [35]

    Random Structures & Algorithms , volume=

    Threshold values of random K-SAT from the cavity method , author=. Random Structures & Algorithms , volume=. 2006 , publisher=

    work page 2006

  36. [36]

    Annals of Probability , volume=

    Suboptimality of local algorithms for a class of max-cut problems , author=. Annals of Probability , volume=. 2019 , publisher=

    work page 2019

  37. [37]

    For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances

    For fixed control parameters the quantum approximate optimization algorithm's objective function value concentrates for typical instances , author=. arXiv preprint arXiv:1812.04170 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  38. [38]

    Physical Review X , volume=

    Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices , author=. Physical Review X , volume=. 2020 , publisher=

    work page 2020

  39. [39]

    Proceedings of the 5th conference on Innovations in theoretical computer science , pages=

    Limits of local algorithms over sparse random graphs , author=. Proceedings of the 5th conference on Innovations in theoretical computer science , pages=

    work page

  40. [40]

    Hartree-Fock on a superconducting qubit quantum computer

    Hartree-Fock on a superconducting qubit quantum computer , author=. arXiv preprint arXiv:2004.04174 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  41. [41]

    Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits

    Spoofing linear cross-entropy benchmarking in shallow quantum circuits , author=. arXiv preprint arXiv:2005.02421 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 2005

  42. [42]

    Quantum Supremacy and the Complexity of Random Circuit Sampling

    Quantum supremacy and the complexity of random circuit sampling , author=. arXiv preprint arXiv:1803.04402 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  43. [43]

    Surveys in Combinatorics , volume=

    Expanders—how to find them, and what to find in them , author=. Surveys in Combinatorics , volume=. 2019 , publisher=

    work page 2019

  44. [44]

    Random graphs, geometry and asymptotic structure , volume=

    Long paths and Hamiltonicity in random graphs , author=. Random graphs, geometry and asymptotic structure , volume=. 2016 , publisher=

    work page 2016

  45. [45]

    Hamilton Cycles in Random Graphs: a bibliography

    Hamilton cycles in random graphs: a bibliography , author=. arXiv preprint arXiv:1901.07139 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  46. [46]

    The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size

    The quantum approximate optimization algorithm and the sherrington-kirkpatrick model at infinite size , author=. arXiv preprint arXiv:1910.08187 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 1910

  47. [47]

    Introduction to the SK model

    Introduction to the SK model , author=. arXiv preprint arXiv:1412.0170 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  48. [48]

    2003 , publisher=

    Spin glasses: a challenge for mathematicians: cavity and mean field models , author=. 2003 , publisher=

    work page 2003

  49. [49]

    Mathematical aspects of mean field spin glass theory

    Mathematical aspects of mean field spin glass theory , author=. arXiv preprint cond-mat/0410435 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  50. [50]

    Physical review letters , volume=

    Solvable model of a spin-glass , author=. Physical review letters , volume=. 1975 , publisher=

    work page 1975

  51. [51]

    Solid State Communications , volume=

    Exactly solvable model of a spin glass , author=. Solid State Communications , volume=. 1976 , publisher=

    work page 1976

  52. [52]

    A sequence of approximated solutions to the

    Parisi, Giorgio , journal=. A sequence of approximated solutions to the. 1980 , publisher=

    work page 1980

  53. [53]

    Talagrand, Michel , journal=. The. 2006 , publisher=

    work page 2006

  54. [54]

    Journal of Statistical Physics , volume=

    The full replica symmetry breaking in the Ising spin glass on random regular graph , author=. Journal of Statistical Physics , volume=. 2018 , publisher=

    work page 2018

  55. [55]

    The Annals of Probability , volume=

    Extremal cuts of sparse random graphs , author=. The Annals of Probability , volume=. 2017 , publisher=

    work page 2017

  56. [56]

    Random Structures & Algorithms , volume=

    Optimization on sparse random hypergraphs and spin glasses , author=. Random Structures & Algorithms , volume=. 2018 , publisher=

    work page 2018

  57. [57]

    Probability Theory and Related Fields , volume=

    Bounds for diluted mean-fields spin glass models , author=. Probability Theory and Related Fields , volume=. 2004 , publisher=

    work page 2004

  58. [58]

    Geometric and Functional Analysis , volume=

    Limits of locally--globally convergent graph sequences , author=. Geometric and Functional Analysis , volume=. 2014 , publisher=

    work page 2014

  59. [59]

    The Annals of Probability , volume=

    The overlap gap property and approximate message passing algorithms for p -spin models , author=. The Annals of Probability , volume=. 2021 , publisher=

    work page 2021

  60. [60]

    The Annals of Probability , volume=

    Local algorithms for independent sets are half-optimal , author=. The Annals of Probability , volume=. 2017 , publisher=

    work page 2017

  61. [61]

    Conference on Learning Theory , pages=

    Free energy wells and overlap gap property in sparse PCA , author=. Conference on Learning Theory , pages=. 2020 , organization=

    work page 2020

  62. [62]

    Classical algorithms and quantum limitations for maximum cut on high-girth graphs

    Classical algorithms and quantum limitations for maximum cut on high-girth graphs , author=. arXiv preprint arXiv:2106.05900 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  63. [63]

    Optimal Low-Degree Hardness of Maximum Independent Set

    Optimal Low-Degree Hardness of Maximum Independent Set , author=. arXiv preprint arXiv:2010.06563 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  64. [64]

    Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics

    Low-degree hardness of random optimization problems , author=. arXiv preprint arXiv:2004.12063 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  65. [65]

    Montanari , booktitle =

    A. Montanari , booktitle =. Optimization of the Sherrington-Kirkpatrick Hamiltonian , year =. doi:10.1109/FOCS.2019.00087 , url =

    work page doi:10.1109/focs.2019.00087 2019

  66. [66]

    Optimization of Mean-field Spin Glasses

    Optimization of mean-field spin glasses , author=. arXiv preprint arXiv:2001.00904 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 2001

  67. [67]

    Optimal transport for applied mathematicians , author=. Birk. 2015 , publisher=

    work page 2015

  68. [68]

    Numerical analysis , volume=

    The conjugate-gradient method for solving linear systems ^1 , author=. Numerical analysis , volume=. 1956 , publisher=

    work page 1956

  69. [69]

    2010 , publisher=

    An introduction to random matrices , author=. 2010 , publisher=

    work page 2010

  70. [70]

    1977 , month = mar, journal =

    Solution of `Solvable model of a spin glass' , author =. 1977 , month = mar, journal =. doi:10.1080/14786437708235992 , urldate =

    work page doi:10.1080/14786437708235992 1977

  71. [71]

    Advances in neural information processing systems , volume=

    Fast matrix square roots with applications to Gaussian processes and Bayesian optimization , author=. Advances in neural information processing systems , volume=

    work page

  72. [72]

    Towards Parisi ultrametricity , author=

    General properties of overlap probability distributions in disordered spin systems. Towards Parisi ultrametricity , author=. Journal of Physics A: Mathematical and General , volume=. 1998 , publisher=

    work page 1998

  73. [73]

    Annals of probability , pages=

    On the high temperature phase of the Sherrington-Kirkpatrick model , author=. Annals of probability , pages=. 2002 , publisher=

    work page 2002

  74. [74]

    Fields Institute Communications , volume=

    Sum rules for the free energy in the mean field spin glass model , author=. Fields Institute Communications , volume=

    work page

  75. [75]

    Physical Review B , volume=

    Extended variational principle for the Sherrington-Kirkpatrick spin-glass model , author=. Physical Review B , volume=. 2003 , publisher=

    work page 2003

  76. [76]

    Mathematical Programming , volume=

    Approximation algorithms for homogeneous polynomial optimization with quadratic constraints , author=. Mathematical Programming , volume=. 2010 , publisher=

    work page 2010

  77. [77]

    Stochastic Processes and their Applications , volume=

    Hoeffding’s inequality for supermartingales , author=. Stochastic Processes and their Applications , volume=. 2012 , publisher=

    work page 2012

  78. [78]

    Journal of statistical physics , volume=

    Random multi-overlap structures and cavity fields in diluted spin glasses , author=. Journal of statistical physics , volume=. 2004 , publisher=

    work page 2004

  79. [79]

    The Number of Partitions of a Set , volume =

    Gian-Carlo Rota , journal =. The Number of Partitions of a Set , volume =

    work page

  80. [80]

    K. P. Choi , journal =. On the Medians of Gamma Distributions and an Equation of Ramanujan , volume =

    work page

Showing first 80 references.