Sharp Phase Transition for Ellipsoid Fitting

Aaron Potechin; Jeff Xu; Madhur Tulsiani; Sofia de la Cerda

REVIEW 3 major objections 5 minor 295 references

Sharp Phase Transition for Ellipsoid Fitting

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read This paper proves a sharp phase transition for ellipsoid fitting: with high probability a centered ellipsoid exists exactly up to $m = (1 \pm o_d(1)) d^2/4$.

desk verdict Plausible resolution of the ellipsoid fitting threshold at d^2/4, but the submitted version is not fully verifiable because the key semicircle/positivity step is deferred to a missing appendix. read the letter →

arxiv 2608.12415 v1 pith:5UN26B5Y submitted 2026-08-12 math.PR

Sofia de la Cerda , Aaron Potechin , Madhur Tulsiani , Jeff Xu This is my paper · ORCID

classification math.PR MSC 60B2090C2252A2060D05

keywords ellipsoidfittingphasetransitionGaussianrandompointssemidefiniteprogramminggraphmatricesorthogonalpolynomialsfreeindependenceMarchenko-Pasturdistribution

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 proves that ellipsoid fitting has a sharp phase transition: for $m$ independent standard Gaussian points in dimension $d$, a centered ellipsoid through all of them exists with high probability when $m \leq (1-o_d(1)) d^2/4$, and no such ellipsoid exists when $m \geq (1+o_d(1)) d^2/4$, where the $o_d(1)$ terms are of order $1/\mathrm{poly}(\log\log d)$. This settles the ellipsoid fitting conjecture up to a vanishing factor. The result matters because the positive-semidefiniteness constraint halves the naive dimension count: the space of $d\times d$ symmetric matrices has dimension about $d^2/2$, and the conjecture says the true feasibility threshold is exactly half of that count. Both directions are established by explicitly constructing SDP witnesses, not by counting arguments.

What carries the argument

The argument is carried by graph matrices and an equivalence between orthogonal polynomials and shape concatenation. A linear combination $K$ of backbone-dangling shapes with $\mathrm{Var}(K) = 1$ is shown to have semicircular spectrum in $[-2, 2]$ up to $o_d(1)$, and its Chebyshev polynomial $P_t(K)$ is approximated, up to $o_d(1)$ in spectral norm, by the sum of graph matrices of all $t$-fold proper concatenations of the shapes in $K$. The same correspondence, with Marchenko-Pastur orthogonal polynomials in place of Chebyshev polynomials, gives an explicit inverse $A^{-1}$ of the main component of the Gram matrix $M$. The correction primitive $\mathrm{correct}(H) = \frac{1}{1-\gamma}(-L^{*}M^{-1}L(H) + \gamma H)$ removes the non-free term $\gamma H$ that a naive projection correction would introduce, and a scalar variance recurrence forces $\mathrm{Var}(Q) = 1$ at $\gamma = 1/2$. A shifted positive function $F_\delta$ with $\gamma = 1/2 - \Theta(\delta)$ then supplies a positive spectral floor that dominates all truncation and early-termination errors.

What would settle it

Concretely, one could run the paper's truncated iterative construction for a large instance, say $d = 10^5$ and $m = \lfloor d^2/4 \rfloor$ with $D = (\log\log d)^a$ and $\delta = D^{-1/2}$, and compute the smallest eigenvalue of $\Lambda = (1/C_\delta) F_\delta^{\leq D}(Q_*) + D_E$; the proof predicts it is at least $\Omega(\delta) > 0$. A negative eigenvalue of magnitude not $o_d(1)$ would falsify Theorem 1.1. Equivalently, one can compute the low-order trace moments of $Q_*$ at $\gamma = 1/2$ and compare them with the semicircle moments of variance 1.

Watch

Extended reading notes

Core claim

Concretely, the paper proves that with probability $1-o_d(1)$, feasibility of fitting a centered ellipsoid through $m$ independent $\mathcal{N}(0, I_d/d)$ points flips at $m = d^2/4$. Below the threshold the witness is a positive semidefinite matrix $\Lambda$ with $v_i^{\top}\Lambda v_i = 1$ for every point $v_i$, built by iteratively correcting the affine deviations of a spectrally transformed inner matrix $Q$. Above the threshold a dual matrix $\Lambda \in \mathrm{span}\{v_i v_i^{\top} : i \in [m]\}$ with $\langle \Lambda, I - R \rangle < 0$ rules out any such ellipsoid. The authors describe this as resolving the ellipsoid fitting conjecture up to a vanishing factor, with $o_d(1)$ instantiated as $1/\mathrm{poly}(\log\log d)$, and note that two concurrent works obtain comparable results.

Load-bearing premise

The whole construction depends on the claim that the iteratively built inner matrix has a semicircular eigenvalue distribution on $[-2,2]$ and total variance 1 up to errors vanishing as $d$ grows; if that spectral and variance control fails at even a vanishing scale, the final matrix $\Lambda$ may fail to be positive semidefinite and the ellipsoid witness collapses.

Editorial extensions

If this is right

Below $m = (1-o_d(1)) d^2/4$, the fitted ellipsoid can be produced by an explicit iterative algorithm with polynomial truncations, rather than shown to exist only non-constructively.
Above $m = (1+o_d(1)) d^2/4$, the dual witness certifies infeasibility, so both sides of the transition are witnessed by explicit SDP solutions.
The threshold $d^2/4$ confirms that the positive-semidefinite constraint imposes exactly a factor-two loss relative to the naive dimension count $d^2/2$.
The vanishing slack of $1/\mathrm{poly}(\log\log d)$ means the transition is sharp up to a very slowly growing factor; the paper makes no attempt to optimize this factor.

Reading between the lines

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

A testable finite-size extension: for fixed $d$, scanning $m$ across $d^2/4$, the smallest eigenvalue of the explicit primal witness should cross zero at $m/d^2 = 1/4 \pm O(1/\mathrm{poly}(\log\log d))$; such simulations could probe whether the $1/\mathrm{poly}(\log\log d)$ slack is tight or an artifact of the proof.
The correction primitive — subtracting the correlated $\gamma M_\tau$ term before iterating — suggests a general recipe for sharp constants in other SDP feasibility problems whose random constraint matrices combine a low-rank term with a Wishart-like component.
Because the variance fixed point at $\gamma = 1/2$ only uses the Chebyshev coefficient identity $\sum_{j\geq 2} b_j^2 = 1 - C_F^2$, the construction may generalize to a family of nonnegative spectral functions $F$, yielding nearby sharp thresholds for related fitting problems.

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

Colleague,

The short version: this paper claims, and plausibly proves, the sharp d^2/4 phase transition for ellipsoid fitting, in both directions, up to o_d(1) slack. If the two main theorems are right, that settles the Saunderson et al. conjecture up to a vanishing factor. That would be a genuine breakthrough. Prior work only reached m ≤ c d^2 with a tiny constant c or d^2/polylog(d), and impossibility only at d^2/2. The construction is explicit: an iterative SDP witness built from graph matrices, extending Potechin-Xu's Lovász theta work. The variance recurrence at γ=1/2 is clean and self-consistent, and the dual refutation mirrors the primal correction almost exactly. This is a serious paper and the authors are honest about concurrent work and about what is deferred.

But the submitted text is not yet a complete proof. Two load-bearing steps are deferred or partially defined. Proposition 5.35, which states that the backtracking residual collapses to the identity up to o_d(1), is given only as a proof sketch with the formal argument pushed to Section C — and Section C is cut off in this version. That cancellation is what makes the Chebyshev polynomial agree with proper concatenations of backbone-dangling shapes; without it, the PSD witness can fail. Similarly, Proposition 5.31 defines an auxiliary B_q(NonIdeal) and then jumps over a summation over shapes to a bound; the skipped intermediate step is exactly where the dependence on maximum shape size D_V is controlled. The displayed line is not verifiable as written. I also noticed a placeholder in Section 3.2 ('as we will discuss in ***'), which suggests the manuscript was not fully polished.

To be clear: I don't think the main claims are wrong. The high-level architecture is coherent, the variance fixed point at 1 is computed from first principles, and the citation pattern looks fair. The problem is certification: the central positivity step is not backed by a complete argument in this version. A referee could not accept the theorems as proven from the submitted PDF.

Who is this for? Anyone working on ellipsoid fitting, SoS lower bounds, or graph-matrix methods. The technique section is worth reading even if the formal details are pending. I'd send it to a serious referee, with the expectation that the authors complete Section C and the missing summation in Prop 5.31 before it can be accepted.

Recommendation: engage with it, but treat the two theorems as claims under construction, not established results. If the deferred proofs check out, this is a major paper.

Referee Report

3 major / 5 minor

Summary. The paper claims to resolve the ellipsoid fitting conjecture up to a vanishing factor: for m independent Gaussian points in R^d, with high probability there is a centered ellipsoid through all points when m ≤ (1-o_d(1)) d^2/4, and no such ellipsoid when m ≥ (1+o_d(1)) d^2/4, with o_d(1) instantiated as 1/poly(log log d). The proof constructs explicit primal and dual SDP witnesses via an iterative process. The inner matrix Q is built from graph matrices of backbone-dangling shapes; the key technical steps are: (1) a Marchenko-Pastur analysis of the Gram matrix M and its inverse; (2) a semicircular spectrum theorem for linear combinations of backbone-dangling shapes with variance 1; (3) a truncation scheme showing that variance-1 and positivity are preserved at the chosen parameters.

Significance. If correct, this resolves a conjecture posed by Saunderson, Chandrasekaran, Parrilo, and Willsky and sharpens a line of work that previously achieved constant-factor thresholds. The proof is constructive and explicit, with concrete formulas for the correction primitive, variance recursions, and parameter choices (e.g., D=t*=(log log d)^a, δ=D^{-1/2}), which is a strength: the construction is not merely existential, and the threshold d^2/4 arises from the fixed-point equation for Var(Q), not from fitting constants to the target. However, the manuscript currently defers or sketches two load-bearing technical steps (the backtracking-residual cancellation for semicircle polynomials and the quantitative bound for non-ideal steps in the norm theorem), which prevents verification of the main theorems as submitted.

major comments (3)

[§5.6, Prop. 5.35] This proposition is load-bearing for the semicircular/Chebyshev step. It asserts that the backtracking intersections of a variance-normalized combination of backbone-dangling shapes collapse to identity: ∥∑_τ c_τ^2 M_{BacktrackingInt(τ)} - I_d∥_sp = o_d(1). The proof is only a two-sentence sketch, and the formal proof is deferred to Section C, which is not present in the visible manuscript (the visible text stops at 'Proposition C.1(Backtracking Residual for S...'). This cancellation is what removes the identity term in P_j(Q) (Lemma 5.33), so that the Chebyshev polynomial is approximated by proper concatenations (Theorem 5.32, Lemma 2.21). If the residual is not o_d(1), the affine-deviation invariant (Prop 2.3) acquires a nonvanishing diagonal term and the final witness Λ may fail PSDness. This step must be proved in the submitted text.
[§5.4, Prop. 5.31 and Thm. 5.18] The quantitative norm bound for non-ideal steps is not verifiable as written. The definition of B_q(NonIdeal) in Theorem 5.18 contains quantities |V(τ)|, c(τ), and |V(τ_i)| that are not specified as a maximum or a summation; Proposition 5.31's proof has a skipped summation where the sum over shapes of |c(τ)|(3∥c∥_1)^{|V(τ)|} is replaced by a constant factor, and the missing intermediate step is exactly where the dependence on D_V is controlled. Without that summation, the advertised d^{-1/2+o(1)} error term and hence the bound ∥K∥_sp ≤ 2+o_d(1) for Var(K)=1 is unsupported. This norm bound is then used to assert the semicircular spectrum of Q and to control the error terms in the final truncation analysis; the gap is load-bearing.
[§5.1, Lemma 5.1] The variance identity Var(correct(τ)) = γ/(1-γ) Var(τ) + o_d(1) drives the scalar recursion that yields Var(Q)=1 at γ=1/2 (Lemma 2.24 and the display in §2.5). However, the proof of Lemma 5.1 is explicitly a sketch: it notes that it has not incorporated polynomial truncation of M^{-1}, it relies on Proposition 5.9 (local charging) whose full analysis is deferred to the appendix, and it asserts without full detail that non-well-behaved vertical intersections have o_d(1) norm. Since the variance normalization is what pins the semicircle radius to 1 and hence the threshold at γ=1/2, the complete block-value argument (including the interaction with truncation) needs to appear.

minor comments (5)

[§3.2] The text contains the unresolved placeholder 'as we will discuss in ***' which should be replaced with a proper cross-reference.
[§2.5] The notation S_i^j is used for (S_i)^j without definition; please define it at first use.
[§6.4] Claim 6.10 states the size bound for D=t^*=(\log d)^a, while the parameter choice two paragraphs earlier is D=t^*=\lceil(\log\log d)^a\rceil; state the constraint a<1 explicitly, as it is needed for D_V=d^{o(1)} and for Remark 6.13's condition.
[Remark 6.13] The condition 'D ≤ c log log d / log log log d' should be reconciled with the chosen D=(log log d)^a; the text should state that a<1 is required.
[References] The reference list includes [KS26] and [MW26] as 'manuscript communicated privately'; if these are to be relied upon, the authors should indicate which parts of the present proof depend on them or clarify that the results are independent.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the d^2/4 threshold emerges from the variance fixed point, not from a fitted input.

full rationale

The derivation is constructive and self-contained in its main lines. The threshold gamma=1/2 is an output: it is the value at which the variance recurrence S_{k+1}=gamma/(1-gamma)(C_F^2+sum_{j>=2} b_j^2 S_k^j) has the fixed point S=1, using the Parseval identity sum b_j^2=1-C_F^2 for the fixed activation F(x)=max(2x,0). F is taken from the authors' prior Lovasz-theta work [PX26], but it is not fitted to the ellipsoid threshold, and the same choice is transparently acknowledged. The correction primitive correct(H)=(1-gamma)^{-1}(-Pi_S H+gamma H) is derived from the graph-matrix expansion of M^{-1}, not assumed. The variance normalization Var(Q)=1 is proved via the graph-matrix variance recurrences (Lemmas 5.1, 2.22-2.24), and the semicircle spectral bound (Theorem 5.18, Theorem 5.32) is proved for any combination of backbone-dangling shapes with variance 1, so applying it to Q does not presuppose the theorem. Self-citations to [PX26, PX25, HKPX23] supply proof techniques and one truncation lemma (Lemma 6.3, citing Lemma D.11 of [PX26]); these are not circular because the cited results do not contain the ellipsoid threshold or the SDP witnesses constructed here. The visible text leaves real gaps: Proposition 5.35 is only a proof sketch deferred to the truncated Appendix C, and Proposition 5.31 skips a summation that controls the D_V dependence. These are completeness/correctness risks, not circularity: a failed cancellation there would break the PSD witness, but it would not make the derivation equivalent to its inputs. Accordingly, no step in the paper reduces by definition or by self-citation to the target theorem.

Assumptions & free parameters 3 free parameters · 4 assumptions · 2 invented entities

The central construction depends on no fitted numerical parameters; all constants are chosen and proven to yield the required o_d(1) bounds. The main assumptions beyond the Gaussian setting are the validity of the cited graph-matrix norm machinery and the internally established free-independence and spectral claims for the new shapes. These are proof-level premises, not physical postulates, so the ledger is short.

free parameters (3)

γ = 2m/d^2 = 2m/d^2
Threshold proxy, not fitted to data. The construction shifts γ by Θ(δ) around 1/2 to force Var(Q)=1.
D = t* = (log log d)^a for fixed a>0
Truncation degrees for the Chebyshev and MP expansions and the iteration depth. Chosen to vanish asymptotically; the result is insensitive to the exact value.
δ = D^{-1/2}
Size of the spectral positivity gap and of the threshold slack; chosen to dominate all truncation errors.

assumptions (4)

domain assumption Independent Gaussian rows v_i ~ N(0, I_d/d).
The problem statement and all graph-matrix constructions are specific to centered Gaussian input; the phase transition may differ for other distributions.
standard math Graph-matrix norm bound machinery from [JPR+22, HKPX23, KPX24, Xu26, KX26, PX26] applies to the newly introduced backbone-dangling shapes.
The paper uses trace-moment block-value bounds from these works as a framework and generalizes them, rather than reproving the framework from scratch.
domain assumption Marchenko-Pastur spectrum of A up to o_d(1) at the edge (Lemma 2.17), enabling the MP polynomial expansion of A^{-1}.
Claim 2.15 is exact on the MP support; the proof must control the spectral edge of A to o_d(1). This is established via Lemma 4.3, and any edge fluctuation would break the inversion expansion.
standard math Free independence of the backbone-dangling graph matrices, giving semicircular spectrum when Var(Q)=1.
This is the key structural claim (Prop. 2.13, Lemma 2.21, Thm 5.18); it is proven via charging arguments, but is a load-bearing premise for the positivity of the SDP witness.

invented entities (2)

backbone-dangling shapes
purpose: Combinatorial decomposition of the inner matrix Q in the iterative process; claimed to be freely independent with controlled variances, yielding semicircular spectrum.
Internal proof objects with no externally falsifiable predictions; their properties are established inside the proof, not by external data.
local-collision pieces (LCP)
purpose: Bookkeeping device that organizes the error terms in the graph-matrix expansion of A^{-1} and Chebyshev polynomials, allowing norm bounds.
Internal combinatorial definitions; no observable consequences outside the proof.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Sharp Phase Transition for Ellipsoid Fitting." pith.science (2026). https://pith.science/paper/5UN26B5Y

@misc{pith2026260812415,
  author       = {Pith},
  title        = {Pith review of: Sharp Phase Transition for Ellipsoid Fitting},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5UN26B5Y}},
  note         = {Machine review of arXiv:2608.12415}
}

abstract

We resolve the ellipsoid fitting conjecture of Saunderson, Chandrasekaran, Parrilo, and Willsky up to a vanishing factor. Concretely, for $m$ independent Gaussian points in dimension $d$, we show that with high probability, for $m \leq (1-o_d(1)) \cdot d^2/4$, there exists a centered ellipsoid passing through all $m$ points; for $m\geq (1+o_d(1) )\cdot d^2/4$, no such ellipsoid exists. This confirms that the ellipsoid fitting problem has a sharp phase transition at $d^2/4$.

Figures

Figures reproduced from arXiv: 2608.12415 by the authors.

**Figure 1.** Graph-matrix representations of a d × d GOE matrix with zero diagonal, and of the m × m matrices Mα and Mβ from eq. (2). Square vertices take labels in [m], and circle vertices take labels in [d]. The two ovals indicate the left and right boundaries Uτ, Vτ. If an edge e is not explicitly labeled with an index, then t(e) = 1 by default. Here, if e = {x, y} is an edge between a square vertex and a circle vertex, then … view at source ↗

**Figure 2.** Examples of shape concatenations. entire concatenated shape α ◦ β. By contrast, the product Mα · Mβ only enforces injectivity separately within the copy of α and within the copy of β. As a result, vertices from α that are not identified through the boundary may nevertheless collide with vertices from β. We now formalize this notion through intersection patterns, which record which vertices from the two shapes collid… view at source ↗

**Figure 4.** Well-behaved Backtracking Intersections Without giving the formal definition of each intersection as it may be transparent from the diagram illustrations alone already, we note that we have three “important” intersection patterns that we call backtracking intersections. Specifically, they are classified with the specific m × m matrix defined in the following. 1. Diamond Backtracking: both of the two inner circle ver… view at source ↗

Figures from the paper (4 more)

**Figure 5.** Figure 5: Examples of graph matrices in the decomposition of [PITH_FULL_IMAGE:figures/full_fig_p026_5.png]

**Figure 6.** Figure 6: Vertical Concatenation and Backbone-Dangling Shapes [PITH_FULL_IMAGE:figures/full_fig_p027_6.png]

**Figure 7.** Figure 7: Examples of intersections. Then we have MτI = m d 2 · MR(τI) + O˜(1/d). With the linearization operation defined, we first identify the properties of the shapes arising from linearization of well-behaved intersections. Claim 5.5. For terms in L ∗ (wτ), the linearizatio…

**Figure 8.** Figure 8: From 2 Intersection Terms to 1 Proper Shape [PITH_FULL_IMAGE:figures/full_fig_p060_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

295 extracted references · 39 canonical work pages

[1]

Local Statistics, Semidefinite Programming, and Community Detection

Jess Banks and Sidhanth Mohanty and Prasad Raghavendra , title =. CoRR , volume =. 2019 , url =. 1911.01960 , timestamp =

work page Pith review arXiv 2019
[2]

Conference on Learning Theory , pages=

Complexity theoretic lower bounds for sparse principal component detection , author=. Conference on Learning Theory , pages=
[3]

Conference On Learning Theory,

Matthew Brennan and Guy Bresler and Wasim Huleihel , title =. Conference On Learning Theory,. 2018 , url =

2018
[4]

SIAM Journal on optimization , volume=

Global optimization with polynomials and the problem of moments , author=. SIAM Journal on optimization , volume=. 2001 , publisher=

2001
[5]

2000 , school=

Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization , author=. 2000 , school=

2000
[6]

Journal of the ACM (JACM) , volume=

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1 , author=. Journal of the ACM (JACM) , volume=. 2015 , publisher=

2015
[7]

ACM Symposium on Discrete Algorithms (SODA) , year=

Extended Formulation Lower Bounds for Refuting Random CSPs , author=. ACM Symposium on Discrete Algorithms (SODA) , year=
[8]

2019 , publisher=

Barak, Boaz and Hopkins, Samuel and Kelner, Jonathan and Kothari, Pravesh K and Moitra, Ankur and Potechin, Aaron , journal=. 2019 , publisher=

2019

Show all 295 references

[9]

Non-backtracking spectrum of random graphs: community detection and non-regular

Bordenave, Charles and Lelarge, Marc and Massouli. Non-backtracking spectrum of random graphs: community detection and non-regular. Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on , pages=. 2015 , organization=

2015
[10]

Linear lower bound on degrees of

Grigoriev, Dima , journal=. Linear lower bound on degrees of. 2001 , publisher=

2001
[11]

Proceedings of the 29th Conference on Learning Theory (COLT) , year =

Boaz Barak and Ankur Moitra , title =. Proceedings of the 29th Conference on Learning Theory (COLT) , year =
[12]

2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

The Power of Sum-of-Squares for Detecting Hidden Structures , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2017 , organization=

2017
[13]

Hopkins and David Steurer , title =

Samuel B. Hopkins and David Steurer , title =. 58th. 2017 , url =. doi:10.1109/FOCS.2017.42 , timestamp =

2017 doi
[14]

Linear level

Schoenebeck, Grant , booktitle=. Linear level. 2008 , organization=

2008
[15]

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

2006
[16]

Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing , series =

Raghavendra, Prasad , title =. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing , series =. 2008 , isbn =. doi:10.1145/1374376.1374414 , acmid =

2008
[17]

Hopkins and Pravesh K

Samuel B. Hopkins and Pravesh K. Kothari and Aaron Potechin and Prasad Raghavendra and Tselil Schramm and David Steurer , title =. CoRR , volume =. 2017 , url =

2017
[19]

Kelner and David Steurer , title =

Boaz Barak and Jonathan A. Kelner and David Steurer , title =. CoRR , volume =. 2013 , url =

2013
[20]

Boaz Barak and Fernando G. S. L. Brand. CoRR , volume =. 2012 , url =

2012
[21]

CoRR , volume =

Boaz Barak and David Steurer , title =. CoRR , volume =. 2014 , url =

2014
[22]

Proceedings of the Thirtieth Annual

Yash Deshpande and Andrea Montanari and Ryan O'Donnell and Tselil Schramm and Subhabrata Sen , title =. Proceedings of the Thirtieth Annual. 2019 , url =. doi:10.1137/1.9781611975482.140 , timestamp =

2019 doi
[23]

Shor, N. Z. Class of global minimum bounds of polynomial functions. Cybernetics. 1987. doi:10.1007/BF01070233

1987 doi
[24]

, title =

Lasserre, Jean B. , title =. SIAM J. on Optimization , issue_date =. 2000 , issn =. doi:10.1137/S1052623400366802 , acmid =

2000 doi
[25]

Lee and Prasad Raghavendra and David Steurer , title =

James R. Lee and Prasad Raghavendra and David Steurer , title =. CoRR , volume =. 2014 , url =

2014
[26]

Hopkins and Jonathan A

Boaz Barak and Samuel B. Hopkins and Jonathan A. Kelner and Pravesh Kothari and Ankur Moitra and Aaron Potechin , title =. CoRR , volume =. 2016 , url =

2016
[27]

O'Rourke, Sean and Vu, Van and Wang, Ke , title =. J. Comb. Theory Ser. A , issue_date =. 2016 , issn =. doi:10.1016/j.jcta.2016.06.008 , acmid =

2016 doi
[28]

Electronic Colloquium on Computational Complexity (ECCC) , year=

Sum-of-squares proofs and the quest toward optimal algorithms , author=. Electronic Colloquium on Computational Complexity (ECCC) , year=
[29]

and Guionnet, Alice and Zeitouni, Ofer , year=

Anderson, Greg W. and Guionnet, Alice and Zeitouni, Ofer , year=. An Introduction to Random Matrices , DOI=
[30]

Universality of Wigner random matrices: a survey of recent results , journal =

Laszlo Erd. Universality of Wigner random matrices: a survey of recent results , journal =. doi:10.1070/rm2011v066n03abeh004749 , url =

doi
[31]

ArXiv , year=

A sub-constant improvement in approximating the positive semidefinite Grothendieck problem , author=. ArXiv , year=
[32]

2006 , volume=

Noga Alon and Assaf Naor , journal=. 2006 , volume=

2006
[33]

Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming , author=. J. ACM , year=
[34]

Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing , series =

Khot, Subhash , title =. Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing , series =. 2002 , isbn =. doi:10.1145/509907.510017 , acmid =

2002
[35]

2018 , pages=

Subhash Khot and Dor Minzer and Shmuel Safra , journal=. 2018 , pages=

2018
[36]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , series =

Khot, Subhash and Minzer, Dor and Safra, Muli , title =. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , series =. 2017 , isbn =. doi:10.1145/3055399.3055432 , acmid =

2017
[37]

Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing , series =

Tulsiani, Madhur , title =. Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing , series =. 2009 , isbn =. doi:10.1145/1536414.1536457 , acmid =

2009
[38]

Physical Review Letters , year=

Solvable Model of a Spin-Glass , author=. Physical Review Letters , year=
[39]

ArXiv , year=

Computing the partition function of the Sherrington-Kirkpatrick model is hard on average , author=. ArXiv , year=
[40]

Andrea Montanari , year=
[41]

Analysis of the ∞ -replica symmetry breaking solution of the Sherrington-Kirkpatrick model , volume =

Crisanti, A and Rizzo, Tommaso , year =. Analysis of the ∞ -replica symmetry breaking solution of the Sherrington-Kirkpatrick model , volume =. Physical review. E, Statistical, nonlinear, and soft matter physics , doi =
[43]

Prasad Raghavendra and David Steurer , title =. In Proc. 50th IEEE Symp. on Foundations of Comp. Sci , year =
[44]

Vijay Bhattiprolu and Venkatesan Guruswami and Euiwoong Lee , booktitle=
[45]

and Li, Jerry , title =

Hopkins, Samuel B. and Li, Jerry , title =. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , series =. 2018 , isbn =. doi:10.1145/3188745.3188748 , acmid =

2018
[46]

Roman Vershynin , title =
[47]

Topics in Random Matrix Theory , author=
[49]

and Parisi, G

Mezard, M. and Parisi, G. and Virasoro, M. , isbn=. 1987 , publisher=

1987
[50]

Mean Field Models for Spin Glasses , author=
[51]

Nishimori, Hidetoshi , biburl =
[52]

Engel, Andreas and Broeck, Christian P. L. Van den , title =. 2001 , isbn =

2001
[53]

2002 , doi =

M. 2002 , doi =. https://science.sciencemag.org/content/297/5582/812.full.pdf , journal =

2002
[54]

2009 , isbn =

Mezard, Marc and Montanari, Andrea , title =. 2009 , isbn =

2009
[55]

Michel Talagrand , year=
[56]

TAP free energy, spin glasses, and variational inference , author=
[57]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , series =

Jain, Vishesh and Koehler, Frederic and Risteski, Andrej , title =. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , series =. 2019 , isbn =. doi:10.1145/3313276.3316299 , acmid =

2019
[58]

CoRR , volume =

Andrej Risteski , title =. CoRR , volume =. 2016 , url =

2016
[59]

Wein and Ahmed El Alaoui and Cristopher Moore , title =

Alexander S. Wein and Ahmed El Alaoui and Cristopher Moore , title =. CoRR , volume =. 2019 , url =

2019
[60]

46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) , year=

On non-approximability for quadratic programs , author=. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) , year=
[61]

Theory of Computing , volume =

Jop Bri. Theory of Computing , volume =. 2017 , url =. doi:10.4086/toc.2017.v013a015 , timestamp =

2017 doi
[62]

Optimization Methods and Software , volume =

Yu Nesterov , title =. Optimization Methods and Software , volume =. 1998 , publisher =. doi:10.1080/10556789808805690 , URL =

1998 doi
[63]

Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity

Dima Grigoriev. Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theoretical Computer Science. 2001. doi:https://doi.org/10.1016/S0304-3975(00)00157-2

2001 doi
[64]

Complexity of Null- and Positivstellensatz proofs

Dima Grigoriev and Nicolai Vorobjov. Complexity of Null- and Positivstellensatz proofs. Annals of Pure and Applied Logic. 2001. doi:https://doi.org/10.1016/S0168-0072(01)00055-0

2001 doi
[65]

Proceedings of the Twenty-Third Annual

Aditya Bhaskara and Moses Charikar and Aravindan Vijayaraghavan and Venkatesan Guruswami and Yuan Zhou , title =. Proceedings of the Twenty-Third Annual. 2012 , url =. doi:10.1137/1.9781611973099.34 , timestamp =

2012 doi
[66]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science , series =

Feige, Uriel and Kim, Jeong Han and Ofek, Eran , title =. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science , series =. 2006 , isbn =. doi:10.1109/FOCS.2006.78 , acmid =

2006 doi
[67]

Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing , series =

Feige, Uriel , title =. Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing , series =. 2002 , isbn =. doi:10.1145/509907.509985 , acmid =

2002
[68]

Statistical Inference and the Sum of Squares Method , Year =

Hopkins, Samuel , School =. Statistical Inference and the Sum of Squares Method , Year =
[69]

Hopkins and Pravesh Kothari and Aaron Henry Potechin and Prasad Raghavendra and Tselil Schramm , title =

Samuel B. Hopkins and Pravesh Kothari and Aaron Henry Potechin and Prasad Raghavendra and Tselil Schramm , title =. 2018 , url =. doi:10.1145/3178538 , timestamp =

2018 doi
[70]

Proceedings of The 28th Conference on Learning Theory,

Yash Deshpande and Andrea Montanari , title =. Proceedings of The 28th Conference on Learning Theory,. 2015 , url =

2015
[72]

Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada , pages =

Tengyu Ma and Avi Wigderson , title =. Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada , pages =. 2015 , url =

2015
[73]

10th Innovations in Theoretical Computer Science Conference,

Aaron Potechin , title =. 10th Innovations in Theoretical Computer Science Conference,. 2019 , url =. doi:10.4230/LIPIcs.ITCS.2019.61 , timestamp =

2019 doi
[74]

CoRR , volume =

Aaron Potechin , title =. CoRR , volume =. 2018 , url =

2018
[75]

Karin Gatermann and Pablo A. Parrilo. Symmetry groups, semidefinite programs, and sums of squares. Journal of Pure and Applied Algebra. 2004. doi:https://doi.org/10.1016/j.jpaa.2003.12.011

2004 doi
[76]

, title =

Raymond, Annie and Saunderson, James and Singh, Mohit and Thomas, Rekha R. , title =. Math. Program. , issue_date =. 2018 , issn =. doi:10.1007/s10107-017-1127-6 , acmid =

2018 doi
[77]

Quick Approximation to Matrices and Applications

Frieze, Alan and Kannan, Ravi. Quick Approximation to Matrices and Applications. Combinatorica. 1999. doi:10.1007/s004930050052

1999 doi
[78]

, journal =

Parisi, G. , journal =. 1979 , month =. doi:10.1103/PhysRevLett.43.1754 , url =

1979 doi
[79]

Random Structures & Algorithms , volume=

Invariant Gaussian processes and independent sets on regular graphs of large girth , author=. Random Structures & Algorithms , volume=. 2015 , publisher=

2015
[80]

Parisi , year=

Giovanni P. Parisi , year=
[81]

Communications in Contemporary Mathematics , volume=

Non-backtracking random walks mix faster , author=. Communications in Contemporary Mathematics , volume=. 2007 , publisher=

2007
[82]

Models of random regular graphs , author=
[83]

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=. 2003 , organization=

2003
[84]

Kunisky, Dmitriy and Bandeira, Afonso S , journal=
[85]

The Annals of Probability , volume=

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

2017
[86]

Random Structures & Algorithms , year=

Spectral techniques applied to sparse random graphs , author=. Random Structures & Algorithms , year=
[87]

2019 , eprint=

High-dimensional estimation via sum-of-squares proofs , author=. 2019 , eprint=

2019
[88]

2021 , eprint=

A Stress-Free Sum-of-Squares Lower Bound for Coloring , author=. 2021 , eprint=

2021
[90]

Advances in Neural Information Processing Systems , volume =

Aaron Potechin and Goutham Rajendran , title =. Advances in Neural Information Processing Systems , volume =. 2022 , note =

2022
[91]

S. R. Allen and R. O'Donnell and D. Witmer , booktitle =. How to Refute a Random CSP , year =. doi:10.1109/FOCS.2015.48 , url =

2015 doi
[92]

SIAM Journal on Computing , volume =

Banks, Jess and Kleinberg, Robert and Moore, Cristopher , title =. SIAM Journal on Computing , volume =. 2019 , doi =. https://doi.org/10.1137/18M1180396 , abstract =

2019 doi
[93]

and Steinhardt, Jacob and Steurer, David , title =

Kothari, Pravesh K. and Steinhardt, Jacob and Steurer, David , title =. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2018 , isbn =. doi:10.1145/3188745.3188970 , abstract =

2018
[94]

2020 , eprint=

Efficient Algorithms for Outlier-Robust Regression , author=. 2020 , eprint=

2020
[95]

2019 , eprint=

Mean Estimation with Sub-Gaussian Rates in Polynomial Time , author=. 2019 , eprint=

2019
[96]

Kothari , title =

Ainesh Bakshi and Pravesh K. Kothari , title =. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. doi:10.1137/1.9781611976465.78 , URL =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611976465.78 , abstract =

2021 doi
[97]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =

Jones, Chris and Potechin, Aaron and Rajendran, Goutham and Xu, Jeff , title =. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =. 2023 , isbn =. doi:10.1145/3564246.3585221 , abstract =

2023
[98]

2022 , eprint=

The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics , author=. 2022 , eprint=

2022
[99]

Wein , title =

Tselil Schramm and Alexander S. Wein , title =. doi:10.1214/22-aos2179 , url =

doi
[100]

2022 , eprint=

Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics , author=. 2022 , eprint=

2022
[101]

2022 , eprint=

Is it easier to count communities than find them? , author=. 2022 , eprint=

2022
[102]

2019 , eprint=

Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio , author=. 2019 , eprint=

2019
[103]

Annual Conference Computational Learning Theory , year=

Is Planted Coloring Easier than Planted Clique? , author=. Annual Conference Computational Learning Theory , year=
[104]

2014 , eprint=

Exact Recovery in the Stochastic Block Model , author=. 2014 , eprint=

2014
[105]

Abbe, Emmanuel , title =. J. Mach. Learn. Res. , month =. 2017 , issue_date =

2017
[106]

Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery , year=

Abbe, Emmanuel and Sandon, Colin , booktitle=. Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery , year=
[107]

Communications on Pure and Applied Mathematics , year=

Proof of the Achievability Conjectures for the General Stochastic Block Model , author=. Communications on Pure and Applied Mathematics , year=
[108]

Spectral redemption in clustering sparse networks , journal =

Florent Krzakala and Cristopher Moore and Elchanan Mossel and Joe Neeman and Allan Sly and Lenka Zdeborov. Spectral redemption in clustering sparse networks , journal =. doi:10.1073/pnas.1312486110 , url =

doi
[109]

2021 , eprint=

Algorithmic Thresholds for Refuting Random Polynomial Systems , author=. 2021 , eprint=

2021
[110]

Liu and S

S. Liu and S. Mohanty and P. Raghavendra , booktitle =. On statistical inference when fixed points of belief propagation are unstable , year =. doi:10.1109/FOCS52979.2021.00047 , url =

2021
[111]

2021 , eprint=

Robust recovery for stochastic block models , author=. 2021 , eprint=

2021
[112]

Combinatorica , month =

Mossel, Elchanan and Neeman, Joe and Sly, Allan , title =. Combinatorica , month =. 2018 , issue_date =. doi:10.1007/s00493-016-3238-8 , abstract =

2018 doi
[113]

Reconstruction and estimation in the planted partition model , volume =

Mossel, Elchanan and Neeman, Joe and Sly, Allan , copyright =. Reconstruction and estimation in the planted partition model , volume =. doi:10.1007/s00440-014-0576-6 , journal =

doi
[114]

Community Detection Thresholds and the Weak Ramanujan Property , year =

Massouli\'. Community Detection Thresholds and the Weak Ramanujan Property , year =. Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing , pages =. doi:10.1145/2591796.2591857 , abstract =
[115]

Hiding Quiet Solutions in Random Constraint Satisfaction Problems , journal =

Florent Krzakala and Lenka Zdeborov. Hiding Quiet Solutions in Random Constraint Satisfaction Problems , journal =. doi:10.1103/physrevlett.102.238701 , url =

doi
[116]

Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications , author =. Phys. Rev. E , volume =. 2011 , month =. doi:10.1103/PhysRevE.84.066106 , url =

2011 doi
[117]

Inference and Phase Transitions in the Detection of Modules in Sparse Networks , author =. Phys. Rev. Lett. , volume =. 2011 , month =. doi:10.1103/PhysRevLett.107.065701 , url =

2011 doi
[118]

Statistical physics of inference: thresholds and algorithms , journal =

Lenka Zdeborov. Statistical physics of inference: thresholds and algorithms , journal =. doi:10.1080/00018732.2016.1211393 , url =

2016
[119]

2020 , eprint=

The Spectrum of the Singular Values of Z-Shaped Graph Matrices , author=. 2020 , eprint=

2020
[120]

Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =

Goutham Rajendran and Madhur Tulsiani , title =. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =. doi:10.1137/1.9781611977554.ch138 , URL =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch138 , abstract =

2023 doi
[121]

and Xu, Jeff , booktitle=

Bafna, Mitali and Hsieh, Jun-Ting and Kothari, Pravesh K. and Xu, Jeff , booktitle=. Polynomial-Time Power-Sum Decomposition of Polynomials , year=
[122]

2022 , eprint=

On Mixing Distributions Via Random Orthogonal Matrices and the Spectrum of the Singular Values of Multi-Z Shaped Graph Matrices , author=. 2022 , eprint=

2022
[123]

Pang, Shuo , TITLE =. 36th. 2021 , MRCLASS =

2021
[124]

Adser\`a, Enric Boix and Brennan, Matthew and Bresler, Guy , TITLE =. 2019. [2019] 2019 , MRCLASS =

2019
[125]

Acta Math

Ding, Jian and Sly, Allan and Sun, Nike , TITLE =. Acta Math. , FJOURNAL =. 2016 , NUMBER =. doi:10.1007/s11511-017-0145-9 , URL =

2016 doi
[126]

, TITLE =

Wormald, Nicholas C. , TITLE =. Ann. Appl. Probab. , FJOURNAL =. 1995 , NUMBER =

1995
[127]

Lauer, Joseph and Wormald, Nicholas , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2007 , NUMBER =. doi:10.1016/j.jctb.2007.02.006 , URL =

2007 doi
[128]

Grimmett, G. R. and McDiarmid, C. J. H. , TITLE =. Math. Proc. Cambridge Philos. Soc. , FJOURNAL =. 1975 , PAGES =. doi:10.1017/S0305004100051124 , URL =

1975 doi
[129]

Approximation, randomization, and combinatorial optimization , SERIES =

Dani, Varsha and Moore, Cristopher , TITLE =. Approximation, randomization, and combinatorial optimization , SERIES =. 2011 , MRCLASS =. doi:10.1007/978-3-642-22935-0\_40 , URL =

2011 doi
[130]

Combinatorica , FJOURNAL =

Chung, Fan and Graham, Ronald , TITLE =. Combinatorica , FJOURNAL =. 2002 , NUMBER =. doi:10.1007/s004930200010 , URL =

2002 doi
[131]

arXiv preprint arXiv:2008.12237 , year=

Spectral planting and hardness of refuting cuts, colorability, and communities in random graphs , author=. arXiv preprint arXiv:2008.12237 , year=

2008 arXiv
[132]

2014 , PAGES =

O'Donnell, Ryan , TITLE =. 2014 , PAGES =. doi:10.1017/CBO9781139814782 , URL =

2014 doi
[133]

Course notes: http://www

Proofs, beliefs, and algorithms through the lens of sum-of-squares , author=. Course notes: http://www. sumofsquares. org/public/index. html , year=
[134]

Lifting sum-of-squares lower bounds: degree-2 to degree-4 , author=
[135]

arXiv preprint arXiv:2009.07269 , year=

Positivity-preserving extensions of sum-of-squares pseudomoments over the hypercube , author=. arXiv preprint arXiv:2009.07269 , year=

2009 arXiv
[136]

Coja-Oghlan, Amin , journal=. The. 2005 , publisher=

2005
[137]

Random Structures & Algorithms , volume=

On independent sets in random graphs , author=. Random Structures & Algorithms , volume=. 2015 , publisher=

2015
[138]

2019 , volume =

Foundations and Trends in Theoretical Computer Science , title =. 2019 , volume =. doi:10.1561/0400000086 , issn =

2019 doi
[139]

2016 , organization=

Polynomial-time tensor decompositions with sum-of-squares , author=. 2016 , organization=

2016
[140]

Gamarnik, David and Sudan, Madhu , TITLE =. Ann. Probab. , FJOURNAL =. 2017 , NUMBER =. doi:10.1214/16-AOP1114 , URL =

2017 doi
[141]

Local algorithms for independent sets are half-optimal , JOURNAL =

Rahman, Mustazee and Vir\'. Local algorithms for independent sets are half-optimal , JOURNAL =. 2017 , NUMBER =. doi:10.1214/16-AOP1094 , URL =

2017 doi
[142]

and Velenik, Y

Friedli, S. and Velenik, Y. , TITLE =. 2018 , PAGES =

2018
[143]

Ghosh, Mrinalkanti and Jeronimo, Fernando Granha and Jones, Chris and Potechin, Aaron and Rajendran, Goutham , TITLE =. 2020. [2020] 2020 , MRCLASS =

2020
[144]

Random graphs , SERIES =

Janson, Svante and. Random graphs , SERIES =. 2000 , PAGES =. doi:10.1002/9781118032718 , URL =

2000 doi
[145]

2020 , booktitle = stoc20, pages =

Mohanty, Sidhanth and O'Donnell, Ryan and Paredes, Pedro , title =. 2020 , booktitle = stoc20, pages =

2020
[146]

2016 , booktitle = stoc16, pages =

Montanari, Andrea and Sen, Subhabrata , title =. 2016 , booktitle = stoc16, pages =

2016
[147]

In Search of Degree-4 Sum-of-Squares Lower Bounds for MaxCut , school=

de Boor, Corwin , year=. In Search of Degree-4 Sum-of-Squares Lower Bounds for MaxCut , school=
[148]

arXiv preprint arXiv:2010.06563 , year=

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

2010 arXiv
[149]

2020 , note =

Rajendran, Goutham and Tulsiani, Madhur , title =. 2020 , note =

2020
[150]

2020 , url =

Potechin, Aaron and Rajendran, Goutham , title =. 2020 , url =

2020
[151]

2019 , eprint=

Computational Hardness of Certifying Bounds on Constrained PCA Problems , author=. 2019 , eprint=

2019
[152]

, TITLE =

Rota, Gian-Carlo and Wallstrom, Timothy C. , TITLE =. Ann. Probab. , FJOURNAL =. 1997 , NUMBER =. doi:10.1214/aop/1024404513 , URL =

1997
[153]

Inequalities (Proc

The arithmetic-geometric inequality , author=. Inequalities (Proc. Sympos. Wright-Patterson Air Force Base, Ohio, 1965) , pages=

1965
[154]

The Parisi formula for mixed p -spin models

Panchenko, Dmitry. The Parisi formula for mixed p -spin models. Ann. Probab. 2014

2014
[155]

Semialgebraic Proofs and Efficient Algorithm Design , title=

N. Semialgebraic Proofs and Efficient Algorithm Design , title=
[156]

Infinite Number of Order Parameters for Spin-Glasses , author =. Phys. Rev. Lett. , volume =. 1979 , month =

1979
[157]

Solvable Model of a Spin-Glass , author =. Phys. Rev. Lett. , volume =. 1975 , month =

1975
[158]

O'Rourke, Sean and Vu, Van and Wang, Ke , title =. J. Comb. Theory Ser. A , month = nov, pages =. 2016 , issue_date =

2016
[159]

High-Dimensional Probability: An Introduction with Applications in Data Science , publisher=

Vershynin, Roman , year=. High-Dimensional Probability: An Introduction with Applications in Data Science , publisher=
[160]

Chan, Siu On , title =. J. ACM , volume =. 2016 , publisher =

2016
[161]

An Introduction to Polynomial and Semi-Algebraic Optimization , DOI=

Lasserre, Jean Bernard , year=. An Introduction to Polynomial and Semi-Algebraic Optimization , DOI=
[162]

and Steurer, David , title =

Barak, Boaz and Kothari, Pravesh K. and Steurer, David , title =. 2017 , pages =

2017
[163]

and Moitra, Ankur and Potechin, Aaron , title =

Barak, Boaz and Hopkins, Samuel and Kelner, Jonathan and Kothari, Pravesh K. and Moitra, Ankur and Potechin, Aaron , title =. SIAM Journal on Computing , volume =. 2019 , doi =. https://doi.org/10.1137/17M1138236 , abstract =

2019 doi
[164]

2017 , isbn =

Mitzenmacher, Michael and Upfal, Eli , title =. 2017 , isbn =

2017
[165]

2018 , note =

Mathematics and Computation , author=. 2018 , note =

2018
[166]

2018 , publisher=

Lectures on Convex Optimization , author=. 2018 , publisher=

2018
[167]

Proceedings of the International Conference IFIP on Theoretical Computer Science, Exploring New Frontiers of Theoretical Informatics , series =

Sudan, Madhu , title =. Proceedings of the International Conference IFIP on Theoretical Computer Science, Exploring New Frontiers of Theoretical Informatics , series =. 2000 , isbn =

2000
[168]

2012 , publisher=

Approximation Algorithms and Semidefinite Programming , author=. 2012 , publisher=

2012
[169]

2019 , note =

Approximating Constraint Satisfaction Problems on High-Dimensional Expanders , author=. 2019 , note =

2019
[170]

ICM , year =

Boaz Barak and David Steurer , title =. ICM , year =
[171]

ICM , year =

Luca Trevisan , title =. ICM , year =
[172]

2015 , isbn =

David, Roee and Dinur, Irit and Goldenberg, Elazar and Kindler, Guy and Shinkar, Igor , title =. 2015 , isbn =

2015
[173]

2019 , note =

Venkatesan Guruswami and Atri Rudra and Madhu Sudan , title =. 2019 , note =

2019
[174]

2017 , isbn =

Ta-Shma, Amnon , title =. 2017 , isbn =

2017
[175]

Klivans and Pravesh K

Sushrut Karmalkar and Adam R. Klivans and Pravesh K. Kothari , title =. CoRR , volume =. 2019 , url =

2019
[176]

CoRR , volume =

Prasad Raghavendra and Morris Yau , title =. CoRR , volume =. 2019 , url =

2019
[177]

The Collected Works of Eugene Paul Wigner , pages=

Characteristic vectors of bordered matrices with infinite dimensions i , author=. The Collected Works of Eugene Paul Wigner , pages=. 1993 , publisher=

1993
[178]

Conference on Learning Theory , pages=

Tensor principal component analysis via sum-of-squares proofs , author=. Conference on Learning Theory , pages=
[179]

Annals of mathematics , pages=

The parisi formula , author=. Annals of mathematics , pages=. 2006 , publisher=

2006
[180]

2005 , publisher=

The umbral calculus , author=. 2005 , publisher=

2005
[181]

Statistical Inference and the Sum of Squares Method , author=
[182]

2017 , organization=

The power of sum-of-squares for detecting hidden structures , author=. 2017 , organization=

2017
[183]

Random Structures & Algorithms , volume=

On the optimality of the random hyperplane rounding technique for MAX CUT , author=. Random Structures & Algorithms , volume=. 2002 , publisher=

2002
[184]

Approximation, Randomization, and Combinatorial Optimization

Bounds on the norms of uniform low degree graph matrices , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) , year=

2016
[185]

2020 , url =

Ahn, Kwangjun and Medarametla, Dhruv and Potechin, Aaron , title =. 2020 , url =

2020
[186]

Optimization of the Sherrington-Kirkpatrick Hamiltonian , year=

A. Optimization of the Sherrington-Kirkpatrick Hamiltonian , year=
[187]

, title =

Kunisky, Dmitriy and Bandeira, Afonso S. , title =. 2019 , url =

2019
[188]

2013 , publisher=

The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions , author=. 2013 , publisher=

2013
[189]

SIGACT News , issue_date =

Aharonov, Dorit and Arad, Itai and Vidick, Thomas , title =. SIGACT News , issue_date =
[190]

Log-Concave Polynomials

Anari, Nima and Liu, Kuikui and Gharan, Shayan Oveis and Vinzant, Cynthia , journal=. Log-Concave Polynomials
[191]

Approximation schemes via

Yoshida, Yuichi and Zhou, Yuan , booktitle=. Approximation schemes via. 2014 , organization=

2014
[192]

Treewidth-based conditions for exactness of the

Wainwright, Martin J and Jordan, Michael I , year=. Treewidth-based conditions for exactness of the
[193]

Guruswami, Venkatesan and Sinop, Ali Kemal , booktitle=focs12, pages=. Faster. 2012 , organization=

2012
[194]

2017 , organization=

On the Bit Complexity of Sum-of-Squares Proofs , author=. 2017 , organization=

2017
[195]

CoRR , volume =

Tali Kaufman and David Mass , title =. CoRR , volume =. 2018 , url =

2018
[196]

arXiv e-prints , keywords =

Random walks on Ramanujan complexes and digraphs. arXiv e-prints , keywords =. 2017

2017
[197]

2012 , note =

Locally testable codes and expanders , author=. 2012 , note =

2012
[198]

Ben-Sasson, Eli and Harsha, Prahladh and Raskhodnikova, Sofya , journal=sicomp, volume=. Some. 2005 , publisher=

2005
[199]

Theory of Computing , volume =

Oveis Gharan, Shayan and Trevisan, Luca , title =. Theory of Computing , volume =. 2015 , pages =. doi:10.4086/toc.2015.v011a009 , publisher =

2015 doi
[200]

Isoperimetric inequalities in simplicial complexes

Parzanchevski, Ori and Rosenthal, Ron and Tessler, Ran J. Isoperimetric inequalities in simplicial complexes. Combinatorica. 2016

2016
[201]

Ramanujan complexes of type \ A d

Lubotzky, Alexander and Samuels, Beth and Vishne, Uzi. Ramanujan complexes of type \ A d. Israel Journal of Mathematics. 2005

2005
[202]

Lubotzky, Alexander and Samuels, Beth and Vishne, Uzi , title =. Eur. J. Comb. , issue_date =. 2005 , pages =

2005
[203]

ICM , year =

Lubotzky, Alexander , title =. ICM , year =
[204]

Isoperimetric Inequalities for Ramanujan Complexes and Topological Expanders

Kaufman, Tali and Kazhdan, David and Lubotzky, Alexander. Isoperimetric Inequalities for Ramanujan Complexes and Topological Expanders. Geometric and Functional Analysis. 2016

2016
[205]

List Decoding with Double Samplers , booktitle = soda19, pages =

Irit Dinur and Prahladh Harsha and Tali Kaufman and Inbal Livni Navon and Amnon Ta. List Decoding with Double Samplers , booktitle = soda19, pages =
[206]

List Decoding with Double Samplers , journal =

Irit Dinur and Prahladh Harsha and Tali Kaufman and Inbal Livni Navon and Amnon Ta. List Decoding with Double Samplers , journal =
[207]

Hoory, Shlomo and Linial, Nathan and Wigderson, Avi , title =. Bull. Amer. Math. Soc. , month = aug, number = 04, pages =
[208]

8th Innovations in Theoretical Computer Science Conference,

Tali Kaufman and David Mass , title =. 8th Innovations in Theoretical Computer Science Conference,
[209]

2014 , pages =

Dinur, Irit and Steurer, David , title =. 2014 , pages =

2014
[210]

2009 , pages =

Impagliazzo, Russell and Kabanets, Valentine and Wigderson, Avi , title =. 2009 , pages =

2009
[211]

Fernando G. S. L. Brand. Product-state approximations to quantum ground states , booktitle =stoc13, pages =
[212]

2012 , pages =

Raghavendra, Prasad and Tan, Ning , title =. 2012 , pages =

2012
[213]

How to Play Unique Games on Expanders

Makarychev, Konstantin and Makarychev, Yury. How to Play Unique Games on Expanders. Approximation and Online Algorithms. 2011

2011
[214]

arXiv e-prints , keywords =

Hypergraph expanders of all uniformities from Cayley graphs. arXiv e-prints , keywords =
[215]

2018 , location =

Kaufman, Tali and Oppenheim, Izhar , title =. 2018 , location =

2018
[216]

Approximation, Randomization, and Combinatorial Optimization

Tali Kaufman and Izhar Oppenheim , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques,
[217]

Approximation, Randomization, and Combinatorial Optimization

Yotam Dikstein and Irit Dinur and Yuval Filmus and Prahladh Harsha , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques,
[218]

Irit Dinur and Tali Kaufman , title =
[219]

Yuval Filmus , title =. Electr. J. Comb. , volume =
[220]

Godsil, Christopher and Meagher, Karen , year=. Erd
[221]

Sum of squares lower bounds for refuting any

Pravesh Kothari and Ryuhei Mori and Ryan O'Donnell and David Witmer , booktitle=stoc17, year=. Sum of squares lower bounds for refuting any
[222]

Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for

Kothari, Pravesh and Meka, Raghu and Raghavendra, Prasad , booktitle=stoc17, year=. Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for
[223]

ACM Transactions on Computation Theory (TOCT) , volume=

On the usefulness of predicates , author=. ACM Transactions on Computation Theory (TOCT) , volume=. 2013 , publisher=

2013
[224]

2015 , organization=

Hardness of graph pricing through generalized max-dicut , author=. 2015 , organization=

2015
[225]

Algorithms -

Sreyash Kenkre and Vinayaka Pandit and Manish Purohit and Rishi Saket , title =. Algorithms -
[226]

Approximating

Khot, Subhash and Saket, Rishi , booktitle=icalp15, year=. Approximating
[227]

Geometric & Functional Analysis GAFA , volume=

Measured descent: A new embedding method for finite metrics , author=. Geometric & Functional Analysis GAFA , volume=. 2005 , publisher=

2005
[228]

The power of

Thapper, Johan and. The power of. arXiv preprint arXiv:1606.02577 , year=

arXiv
[229]

The complexity of finite-valued

Thapper, Johan and. The complexity of finite-valued. 2013 , organization=

2013
[230]

The power of linear programming for general-valued

Kolmogorov, Vladimir and Thapper, Johan and. The power of linear programming for general-valued. SIAM Journal on Computing , volume=44, number=1, pages=
[231]

Approximate constraint satisfaction requires large

Chan, Siu On and Lee, James and Raghavendra, Prasad and Steurer, David , booktitle=focs13, pages=. Approximate constraint satisfaction requires large. 2013 , organization=

2013
[232]

Surveys in Combinatorics , year = 2007, volume = 346, pages =

Johan H stad , title =. Surveys in Combinatorics , year = 2007, volume = 346, pages =

2007
[233]

Theory of Computing , volume =

Siavosh Benabbas and Konstantinos Georgiou and Avner Magen and Madhur Tulsiani , title =. Theory of Computing , volume =. 2012 , pages =

2012
[234]

A characterization of strong approximation resistance , author=
[235]

Approximating a finite metric by a small number of tree metrics , author=
[236]

, title =

Barak, Boaz and Chan, Siu On and Kothari, Pravesh K. , title =. 2015 , isbn =. doi:10.1145/2746539.2746625 , acmid =

2015
[237]

Random Structures Algorithms , FJOURNAL =

Bhattacharyya, Arnab and Grigorescu, Elena and Shapira, Asaf , TITLE =. Random Structures Algorithms , FJOURNAL =. 2015 , NUMBER =. doi:10.1002/rsa.20507 , URL =

2015 doi
[238]

Bhattacharyya, Arnab and Grigorescu, Elena and Raghavendra, Prasad and Shapira, Asaf , TITLE =. Combin. Probab. Comput. , FJOURNAL =. 2012 , NUMBER =. doi:10.1017/S0963548312000363 , URL =

2012 doi
[239]

Approximation, randomization, and combinatorial optimization , SERIES =

Fu, Hu and Kleinberg, Robert , TITLE =. Approximation, randomization, and combinatorial optimization , SERIES =. 2014 , MRCLASS =

2014
[240]

Theory of Computing , volume =

Robert Krauthgamer and Tim Roughgarden , title =. Theory of Computing , volume =. 2011 , pages =. doi:10.4086/toc.2011.v007a005 , publisher =

2011 doi
[241]

Geometric And Functional Analysis , pages=

Bounds for graph regularity and removal lemmas , author=. Geometric And Functional Analysis , pages=. 2011 , publisher=

2011
[242]

Lower bounds for testing triangle-freeness in Boolean functions , author=. Proc. 21st Ann. ACM-SIAM Symp. on Discrete Algorithms , pages=. 2010 , organization=

2010
[243]

Journal of Combinatorial Theory, Series A , volume=

A combinatorial proof of the removal lemma for groups , author=. Journal of Combinatorial Theory, Series A , volume=. 2009 , publisher=

2009
[244]

Subhash Khot , title =
[245]

Subhash Khot and Rishi Saket , title =
[246]

Prasad Raghavendra and David Steurer and Madhur Tulsiani , title =
[247]

APPROX-RANDOM , year =

Sanjeev Arora and Rong Ge , title =. APPROX-RANDOM , year =
[248]

Foundations and Trends in Machine Learning , volume = 4, number = 2, year = 2012, pages =

Shai Shalev-Shwartz , title =. Foundations and Trends in Machine Learning , volume = 4, number = 2, year = 2012, pages =

2012
[249]

Mirror descent and nonlinear projected subgradient methods for convex optimization

Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters. 2003. doi:10.1016/S0167-6377(02)00231-6

2003 doi
[250]

SIGACT News , volume = 40, number = 2, year = 2009, pages =

Luca Trevisan , title =. SIGACT News , volume = 40, number = 2, year = 2009, pages =

2009
[251]

2007 , pages =

Terence Tao , title =. 2007 , pages =

2007
[252]

Random Structures Algorithms , FJOURNAL =

Alon, Noga , TITLE =. Random Structures Algorithms , FJOURNAL =. 2002 , NUMBER =. doi:10.1002/rsa.10056 , ZBLNUMBER =

2002 doi
[253]

Annals of Mathematics , volume = 174, number = 1, pages =

Fox, Jacob , title =. Annals of Mathematics , volume = 174, number = 1, pages =
[254]

Surveys in Combinatorics 2013 , year=

Graph removal lemmas , author=. Surveys in Combinatorics 2013 , year=

2013
[255]

Emerging Applications of Algebraic Geometry (of IMA Volumes in Mathematics and its Applications) , year =

Monique Laurent , title =. Emerging Applications of Algebraic Geometry (of IMA Volumes in Mathematics and its Applications) , year =
[256]

, title =

Bourgain, J. , title =. Israel Journal of Mathematics , publisher =
[257]

Guy Kindler and Ryan O'Donnell , title =
[258]

Omer Reingold and Luca Trevisan and Madhur Tulsiani and Salil Vadhan , title =
[259]

Encyclopedia of Operations Research and Management Science

Madhur Tulsiani , title =. Encyclopedia of Operations Research and Management Science. 2010 , publisher =

2010
[260]

Handbook on Semidefinite, Cone and Polynomial Optimization , year =

Eden Chlamtac and Madhur Tulsiani , title =. Handbook on Semidefinite, Cone and Polynomial Optimization , year =
[261]

and Szemer\'edi, Endre , TITLE =

Ruzsa, Imre Z. and Szemer\'edi, Endre , TITLE =. Combinatorics,. 1978 , MRCLASS =

1978
[262]

FOCS , year =

Arnab Bhattacharyya and Swastik Kopparty and Grant Schoenebeck and Madhu Sudan and David Zuckerman , title =. FOCS , year =
[263]

Dima Grigoriev , title =. Theor. Comput. Sci. , volume =. 2001 , pages =

2001
[264]

Terence Tao , title =
[265]

Razborov , title =

Michael Alekhnovich and Alexander A. Razborov , title =. FOCS , year =
[266]

SIAM Journal on Optimization , volume =

Daniel Bienstock and Mark Zuckerberg , title =. SIAM Journal on Optimization , volume =. 2004 , pages =

2004
[267]

Complexity Analyses of

Yu-Hin Au and Levent Tun. Complexity Analyses of. IPCO , year =
[268]

Transactions of the American Mathematical Society , jstor_issuetitle =

Forbidden Intersections , author =. Transactions of the American Mathematical Society , jstor_issuetitle =
[269]

Siu-On Chan , title =
[270]

Madhur Tulsiani and Pratik Worah , title =
[271]

Subhash Khot and Muli Safra and Madhur Tulsiani , title =
[272]

Eli Ben-Sasson and Noga Ron-Zewi and Madhur Tulsiani and Julia Wolf , title =
[273]

CoRR , volume =

Timothy Gowers , title =. CoRR , volume =
[274]

STOC , year =

Paul Beame and Trinh Huynh and Toniann Pitassi , title =. STOC , year =
[275]

Boaz Barak and Fernando G. S. L. Brand. Hypercontractivity, Sum-of-Squares Proofs, and their Applications , journal =. 2012 , ee =

2012
[276]

2011 , pages =

Boaz Barak and Prasad Raghavendra and David Steurer , title =. 2011 , pages =

2011
[277]

Making the long code shorter, with applications to the Unique Games Conjecture , journal =

Boaz Barak and Parikshit Gopalan and Johan H. Making the long code shorter, with applications to the Unique Games Conjecture , journal =
[278]

APPROX-RANDOM , year =

Eden Chlamtac and Gyanit Singh , title =. APPROX-RANDOM , year =
[279]

Samorodnitsky , title =

A. Samorodnitsky , title =. 2007 , pages =

2007
[280]

SIGACT News , volume =

Madhu Sudan , title =. SIGACT News , volume =. 2000 , pages =

2000
[281]

Foundations and Trends in Theoretical Computer Science , volume =

Venkatesan Guruswami , title =. Foundations and Trends in Theoretical Computer Science , volume =
[282]

FOCS , year =

Venkatesan Guruswami and Ali Kemal Sinop , title =. FOCS , year =
[283]

Electronic Colloquium on Computational Complexity (ECCC) , volume =

Shachar Lovett , title =. Electronic Colloquium on Computational Complexity (ECCC) , volume =. 2010 , pages =

2010
[284]

Viola , title =

E. Viola , title =. 2007 , notes =

2007
[285]

and Szemer\'edi, E

Sudakov, B. and Szemer\'edi, E. and Vu, V.H. , journal =. On a question of. 2005 , number =

2005
[286]

and Vu, V

Tao, T. and Vu, V. , Date-Added =. Additive combinatorics , Year =
[287]

, TITLE =

Ruzsa, I.Z. , TITLE =. Ast\'erisque , FJOURNAL =. 1999 , PAGES =

1999
[288]

Green, Ben , affiliation =. A. Geometric And Functional Analysis , publisher =
[289]

and Tao, T

Green, B.J. and Tao, T. , Date-Added =. Arxiv preprint arXiv:0906.3100 , Title =

arXiv
[290]

and Wolf, J

Gowers, T. and Wolf, J. , TITLE =. Proc. Lond. Math. Soc. (3) , FJOURNAL =. 2010 , NUMBER =. doi:10.1112/plms/pdp019 , URL =

2010 doi
[291]

and Wolf, J

Gowers, T. and Wolf, J. , Title =. Mathematika , VOLUME =. 2012 , NUMBER =. doi:10.1112/S0025579311001264 , URL =

2012 doi
[292]

and Wolf, J

Gowers, T. and Wolf, J. , Date-Added =. To appear, J. Anal. Math., arXiv:1002.2210 , Title =

arXiv
[293]

, Date-Added =

Sanders, T. , Date-Added =. Submitted, arXiv:1011.0107 , Title =

arXiv
[294]

and Wolf, J

Tulsiani, M. and Wolf, J. , Journal =. Quadratic
[295]

, TITLE =

Candela, P. , TITLE =. Bull. Lond. Math. Soc. , FJOURNAL =. 2010 , NUMBER =. doi:10.1112/blms/bdp074 , URL =

2010 doi
[296]

and Sisask, O

Croot, E. and Sisask, O. , Date-Added =. Submitted, arXiv:1003.2978 , Title =

arXiv
[297]

, Date-Added =

Petridis, G. , Date-Added =. Preprint, arXiv:1101.2532 , Title =

arXiv
[298]

, Date =

Gowers, T. , Date =. A new proof of. Geom. Func. Anal. , Number =
[299]

, TITLE =

Green, B.J. , TITLE =. Additive combinatorics , SERIES =. 2007 , MRCLASS =

2007
[300]

``An Irregular Mind: Szemer\'edi is 70'' Bolyai Society Math

An arithmetic regularity lemma, an associated counting lemma, and applications , author=. ``An Irregular Mind: Szemer\'edi is 70'' Bolyai Society Math. Studies 21 , pages=. 2010 , publisher=

2010

Pith tools

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

[1] [1]

Local Statistics, Semidefinite Programming, and Community Detection

Jess Banks and Sidhanth Mohanty and Prasad Raghavendra , title =. CoRR , volume =. 2019 , url =. 1911.01960 , timestamp =

work page Pith review arXiv 2019

[2] [2]

Conference on Learning Theory , pages=

Complexity theoretic lower bounds for sparse principal component detection , author=. Conference on Learning Theory , pages=

[3] [3]

Conference On Learning Theory,

Matthew Brennan and Guy Bresler and Wasim Huleihel , title =. Conference On Learning Theory,. 2018 , url =

2018

[4] [4]

SIAM Journal on optimization , volume=

Global optimization with polynomials and the problem of moments , author=. SIAM Journal on optimization , volume=. 2001 , publisher=

2001

[5] [5]

2000 , school=

Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization , author=. 2000 , school=

2000

[6] [6]

Journal of the ACM (JACM) , volume=

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1 , author=. Journal of the ACM (JACM) , volume=. 2015 , publisher=

2015

[7] [7]

ACM Symposium on Discrete Algorithms (SODA) , year=

Extended Formulation Lower Bounds for Refuting Random CSPs , author=. ACM Symposium on Discrete Algorithms (SODA) , year=

[8] [8]

2019 , publisher=

Barak, Boaz and Hopkins, Samuel and Kelner, Jonathan and Kothari, Pravesh K and Moitra, Ankur and Potechin, Aaron , journal=. 2019 , publisher=

2019