Pith. sign in

REVIEW 6 minor 58 references

A normalized Kikuchi matrix achieves the conjectured sample–time trade-off for planted noisy kXOR, with no logarithmic loss, at every arity.

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 · deepseek-v4-flash

2026-08-03 02:04 UTC pith:AJSB2AC6

load-bearing objection Log-free Kikuchi spectral trade-off for kXOR: genuinely new, technically dense, and mostly supported; the 'sharp' claim is narrower than the title suggests, but the paper says so.

arxiv 2607.29672 v1 pith:AJSB2AC6 submitted 2026-07-31 cs.DS cs.CCquant-ph

The Kikuchi Hierarchy is Sharp for kXOR

Alexander Schmidhuber , Matthew B. Hastings This is my paper
classification cs.DS cs.CCquant-ph MSC 68Q2568W2005C8060C05
keywords Kikuchi hierarchyplanted kXORstrong refutationspectral algorithmslow-degree lower boundstrace methodrandom constraint satisfactionsum-of-squares certificates
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's goal is to settle the conjectured trade-off between signal strength and running time for planted noisy kXOR: level ℓ of the Kikuchi hierarchy should solve the problem whenever the clause count m is at least a constant multiple of ρ^{-2} n^{k/2}/ℓ^{k/2−1}, with no hidden polylogarithmic loss. The authors prove this for strong detection, weak recovery, and two-sided strong refutation, at every arity k ≥ 3, after normalizing the Kikuchi matrix by the degree plus a mean floor. The normalization removes a localization obstruction—high-degree rows that create spurious large eigenvalues—and a sharp trace-walk count shows the null norm is bounded by sqrt(ℓ/(rd+ℓ)). Matching lower bounds in the same fixed-sample model show the curve cannot be pushed down further within sign-degree-bounded statistics, and the results also yield sum-of-squares certificates and a quartic quantum speedup.

Core claim

On the paper's terms, the central claim is that a normalized Kikuchi hierarchy attains the conjectured log-free curve m ≳ ρ^{-2} n^{k/2}/ℓ^{k/2-1} for strong detection, weak recovery, and two-sided strong refutation, for all k ≥ 2 in the stated level range. The proof hinges on reweighting by Γ = D + \bar d I at even arity and by a capped rooted-pair completion at odd arity, then bounding the null spectrum by a trace expansion over closed walks: openings are charged through the identity M_S/(d+M_S)+d/(d+M_S)=1, and closings through a parity bound on active legal residuals with an excess parameter χ counting recycled vertices. The same walk count underlies the lower bounds as an ordered count

What carries the argument

The central object is the normalized level-ℓ Kikuchi matrix—the level-ℓ Kikuchi matrix is the signed adjacency matrix between ℓ-element subsets given by parity clauses, and the normalized variant divides by the degree-plus-mean diagonal Γ^{-1/2} = (D+\bar d I)^{-1/2} (at odd arity, a capped rooted-pair completion plays the same role). The workhorse argument is the trace expansion over closed walks, with a branchwise charging scheme that replaces any maximum-degree union bound by the identity (1.3) and an active-label parity lemma (Lemma 5.1) that counts how many active clauses can be legal at a row; the excess χ charges each recycled vertex by O(t/n). These yield the log-free null norm bound

Load-bearing premise

The entire log-free spectral bound rests on the branchwise mass hypotheses: after any fixed branch prefix, freshly introduced legal labels must have conditional expected mass at most d(C_r t/n)^h when they recycle h previously exposed vertices, and the retention/diagonal must be monotone (insertion-nonincreasing and insertion-nondecreasing, respectively); if this fails at any arity or step, the null norm bound ∥K∥ ≲ sqrt(ℓ/(rd+ℓ)) can break, and planted/null separation collap

What would settle it

Take a null instance of even-arity kXOR with n large, k=4, ℓ=2, and m = C n^2 (the conjectured threshold with ρ fixed); compute the top eigenvalue of K = (D+\bar d I)^{-1/2} A (D+\bar d I)^{-1/2} for many draws. If the empirical null norm exceeds the predicted constant multiple of sqrt(ℓ/(r\bar d+ℓ)) by any polylogarithmic factor with nonvanishing probability, the sharp bound is false. Alternatively, simulate the branchwise process and measure the conditional mass in (5.6) for h=1,2,3; a single violation for a random prefix would refute the mass hypothesis.

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

If this is right

  • At the conjectured threshold, the runtime exponent n^{ℓ+O_k(1)} no longer suffers a superpolynomial slowdown from polylog factors: the level required at density Δ is ℓ ≍ n/(ρ^2 Δ)^{2/(k-2)} exactly as predicted.
  • Two-sided strong refutation of random kXOR is possible on the same log-free curve with sound pointwise certificates that can be evaluated exactly and turned into degree-O_k(ℓ) sum-of-squares proofs.
  • Matching sign-degree lower bounds show that no statistic of sign degree O(ℓ), even with arbitrary preprocessing of the support hypergraph, can detect or recover below the curve, making the spectral algorithms tight within that class.
  • An independent sample of O_k(ρ^{-2} n log(1/ϑ)) clauses boosts weak recovery to error ϑ (and exact recovery), matching the total-sample minimax rate.
  • For slowly growing levels, a quantum algorithm achieves detection and weak recovery with gate complexity N_L^{1/4+o(1)} poly(n), a quartic speedup in the Kikuchi dimension over the classical spectral algorithms.

Where Pith is reading between the lines

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

  • The branchwise charging identity and the excess counting should transfer to Kikuchi-type operators for other sparse planted CSPs whose clauses behave as partial matchings on the slice, potentially yielding log-free bounds for those hierarchies as well.
  • Because the normalization tames only extreme row degrees, the paper suggests that any spectral construction that avoids maximum-degree union bounds—not just this specific one—will reach the log-free curve; one testable extension is to non-spectral color-coding algorithms, which may be adapted to remove their level-range restriction.
  • The paper's odd-arity construction leaves a gap at vanishing bias ρ ≪ (ℓ/n)^{1/4}; a natural next step is an operator that controls dense root cells without discarding a constant fraction of the pair polynomial, which would extend the log-free curve to the full parameter range.
  • The trace-walk count used here is closely related to the hypergraph Moore bound; one could seed automated proof systems with the branchwise charging pattern to certify log-free spectral bounds for other random hypergraph operators.

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

0 major / 6 minor

Summary. The paper studies planted noisy kXOR and random kXOR refutation. Its central claim is that a normalized variant of the Kikuchi hierarchy attains the conjectured log-free trade-off (1.1) at every level in (2.3): strong detection and weak recovery (Theorem 2.2), an exact-recovery cleanup (Theorem 2.3), two-sided strong refutation with explicit sum-of-squares certificates (Theorem 2.5), matching low-degree lower bounds in the same fixed-m model (Theorem 2.6), a quantum detection/recovery algorithm (Theorem 12.7), and a transfer to Boolean CSPs (Section 13). The technical core is a sharp trace bound for the normalized operator: closed walks are analyzed through an opening/closing accounting with an excess parameter, and the degree-plus-floor normalizer avoids the maximum-degree logarithm that appears in prior work. The two trace theorems (Theorems 5.3 and 5.5) are stated with explicit hypotheses, and the applications in Sections 6, 7, and 9 check those hypotheses. The paper is exceptionally dense but internally coherent; the companion use in the hypergraph Moore bound is also noted.

Significance. If correct, the paper resolves a gap that has been open since the Kikuchi hierarchy was introduced: removing all polylogarithmic factors from the spectral sample-complexity curve for sparse kXOR. The proof strategy is substantial and well matched to the difficulty: the trace expansion is organized around a small set of structural hypotheses, the lower bounds are obtained by direct ordered boundary counts in the same fixed-m model, and the refutation certificates are genuinely sound on every input, not merely likely correct. The paper is also commendably honest about the scope of its lower bounds: Remarks 2.9 and 11.8 state clearly that the inference converses are low-degree and not unconditional runtime lower bounds, and the refutation lower-bound row in Table 1 is not matched by a new canonical sum-of-squares lower bound. I did not find a concrete algebraic or probabilistic error, and the stress-test concern about mass hypotheses (5.6) and (P1)-(P4) does not land as a flaw: the applications in Sections 6.1, 7.3, and 9.3 are internally consistent. The main remaining risk is the sheer density of the verification, not a specific detected mistake.

minor comments (6)
  1. [Abstract and Section 2] The abstract says 'at every arity k >= 3', while Theorem 2.2 and the surrounding text include k = 2. This is a minor overstatement; the abstract should say k >= 2 and note that the k = 2 curve is flat.
  2. [Abstract, Theorem 2.6, Remark 2.9] The phrase 'matching lower bounds' in the abstract and in Table 1 should be qualified at first mention: the matching is against sign-degree-O(ell) statistics with arbitrary support preprocessing, not against all polynomial-time algorithms. The paper is careful about this later, but the abstract currently reads as an unconditional computational lower bound.
  3. [Sections 5.5, 7.3, 9.3] The verification of mass hypotheses (P4) is compressed to a few sentences in each application. I checked the counts and found them consistent, but because a single failure would reintroduce a logarithmic factor, the paper would benefit from displaying the exact ordered counts for the three cases in (5.11)-(5.13) in one place, e.g., an appendix.
  4. [Section 9.3, Eq. (9.14)] The asymptotic relation d_* = Theta_r(n mu_0^2) is used in the proof of Proposition 9.3 and Lemma 9.4. The two-sided inequality with explicit constants c_r, C_r is not displayed; stating it inline would make the range of validity of (9.12) easier to audit.
  5. [Section 12.4] The tomography argument says that estimating every entry of the one-particle density matrix to accuracy n^{-2} controls the operator norm at scale 1/n. This is standard, but the sentence is terse; a short justification or a pointer to a standard perturbation inequality would help the reader.
  6. [Section 14] The AI-use statement is transparent and does not affect my assessment. If the journal has a disclosure policy, the authors should ensure the statement conforms to it.

Circularity Check

0 steps flagged

No significant circularity: the classical trace-based derivation is self-contained relative to the stated model assumptions, and no fitted parameter is renamed as a prediction.

full rationale

The central chain (Theorems 5.3/5.5 to Propositions 6.1/7.4/9.3 to Theorems 2.2/2.5) is not circular. The floor d is not fitted to the target curve: in the even case it is the model-computed mean row degree dbar = Theta_r(mbar ell^r / n^r) from (6.2), and in the odd cases it is the Poisson/cell intensity d = n alpha^2 or the fixed-sample d_* computed from the clause count; each application verifies the trace theorem's mass hypotheses (5.6) and (P1)-(P4) directly from the i.i.d. or Poisson support law rather than postulating the theorem's conclusion. The lower bounds are independent of the upper-bound trace machinery: Section 11 is explicitly self-contained given Section 2 and derives its conclusions from the ordered boundary count of Lemma 11.4, not from the spectral estimates. Self-citations such as the companion Moore-bound paper [1] and the quantum framework [12] are contextual or used as black boxes only for peripheral extensions; the main inference and refutation results do not rest on them. The paper also explicitly disclaims unconditional runtime lower bounds in Remark 2.9 and Remark 11.8, which narrows the force of the word 'sharp' but is a scope limitation, not circularity. No equation is shown to reduce to its own input by construction, and no fitted parameter is relabeled as a prediction.

Axiom & Free-Parameter Ledger

1 free parameters · 6 axioms · 1 invented entities

The theorems do not fit constants to data. The only hand-chosen design element is the odd-arity dummy-candidate intensity; all other quantities are fixed by prior literature or by the model. The main interpretive assumption is that low-degree sign statistics constitute the relevant lower-bound class, which the paper itself flags.

free parameters (1)
  • Dummy candidate intensity q (odd arity) = q = D_+^{-1}; realness probability alpha = pi D_+ = Theta(rho^{-2} sqrt(ell/n))
    Chosen by hand to cap expected occupancy of each root-row cell and smooth the planted mean; a design parameter of the odd-arity construction, not fitted to the target trade-off.
axioms (6)
  • domain assumption Planted noisy kXOR fixed-m model with replacement: supports i.i.d. uniform k-subsets, labels independent with bias rho; fixed k, rho, delta and level range (2.3).
    This is the problem model in Section 2; all theorems are stated in this fixed-m model.
  • standard math Poisson subsampling couples the fixed-m model to independent Poisson pools (Lemma 4.1); Markov/Mecke equations and exchangeability deletion bounds (Lemma 4.2) justify branchwise trace estimates.
    Used in Section 4.2 and throughout the trace theorems.
  • standard math Trace method: operator norm is bounded by high even moments plus Markov; sign averaging kills walks with odd clause multiplicities.
    Core mechanism of Theorems 5.3 and 5.5.
  • domain assumption Low-degree sign-statistic class (Definition 11.1) is the chosen converse model; it is used as evidence of computational sharpness.
    The lower bounds are theorem-level for this class; Remark 11.8 explicitly notes this is not an unconditional runtime lower bound.
  • standard math Random-start Krylov/Lanczos guarantee and exact rational inertia evaluation are taken as prior results.
    Lemmas 4.6 and Section 4.4 rely on standard numerical linear algebra.
  • domain assumption Guided sparse-Hamiltonian framework of [12] supplies the quantum guide state and its preparation cost.
    Section 12 imports the framework and its assumptions verbatim; parity-freeness is argued in Lemma 12.1.
invented entities (1)
  • Dummy candidate process (odd arity) no independent evidence
    purpose: Pads every rooted type to a common candidate intensity, smoothing the planted mean into a Johnson matrix and keeping the linear part of the centered planted matrix small.
    This is an algorithmic construction, not an empirical entity; it has no falsifiable handle outside the paper, but its effect is explicitly controlled in Proposition 7.5.

pith-pipeline@v1.3.0-daily-deepseek · 52527 in / 18921 out tokens · 198784 ms · 2026-08-03T02:04:35.830737+00:00 · methodology

0 comments
read the original abstract

Planted noisy $k$XOR and the strong refutation of random $k$XOR are governed by a conjectured trade-off between signal strength and time: Level $\ell$ of the Kikuchi hierarchy should achieve the smooth curve \begin{equation*} m\ \gtrsim\ \rho^{-2}n^{k/2}/\ell^{k/2-1}\ \text{clauses} \quad\Longleftrightarrow\quad \text{solvable in time }n^{O(\ell)}, \end{equation*} where $\rho$ is the bias of the planted signal or, for refutation, the target advantage. However, every spectral analysis of sparse $k$XOR to date loses polylogarithmic factors against this curve, a loss that enters the exponent of the running time. We show that a normalized variant of the Kikuchi hierarchy achieves the sharp conjectured trade-off, with no logarithmic loss, at every arity $k\ge3$. At the scale above, our algorithms achieve strong detection, weak recovery, and strong refutation; an additional cleanup step boosts weak recovery to exact recovery, and the refutation certificates yield sum-of-squares proofs of degree $O_k(\ell)$. We also prove matching lower bounds in the same model. The inference and refutation upper bounds transfer to more general planting laws and predicates. Finally, we give a quantum algorithm that achieves a quartic speedup over the classical spectral algorithms for detection and weak recovery. The proofs rest on two key ingredients: a normalization of the sparse Kikuchi matrix, and a sharp count of the closed walks in its trace expansion. We use a closely related trace-walk count to prove Feige's 2008 hypergraph Moore bound conjecture in a companion paper.

Figures

Figures reproduced from arXiv: 2607.29672 by Alexander Schmidhuber, Matthew B. Hastings.

Figure 1
Figure 1. Figure 1: A surviving trace walk of length 2t = 8 with clause labels a, b, c, d. Each step is an opening (O) or a closing (C) of an active label; a step is an opening when its label is fresh, or seen before but currently inactive. There are exactly t of each. Openings are charged by the identity (1.3); closings are charged through the parity bound of Lemma 5.1 on active legal labels. A fresh label that reuses previo… view at source ↗
Figure 2
Figure 2. Figure 2: The algorithm of Theorem 2.2. Only the operator built in Step 2 and the acceptance [PITH_FULL_IMAGE:figures/full_fig_p033_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The algorithm of Theorem 2.5. 9 Refutation: sound certificates at both parities This section constructs the certificates behind Theorem 2.5; exact evaluation and the sum-of-squares proofs follow in Section 10. A certificate may not subsample: it must account for every clause of the given input. At even arity this costs nothing: the normalized matrix of Section 6, built from the full input, is already a det… 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

58 extracted references · 1 canonical work pages

  1. [1]

    Schmidhuber and M

    A. Schmidhuber and M. B. Hastings,A spectral proof of the hypergraph Moore bound, arXiv:2607.26028 (2026)

    Pith/arXiv arXiv 2026

  2. [2]

    Zdeborov´ a and F

    L. Zdeborov´ a and F. Krzakala,Statistical physics of inference: thresholds and algorithms, Adv. Phys. 65 (2016), 453–552

    2016

  3. [3]

    A. S. Bandeira, A. Perry, and A. S. Wein,Notes on computational-to-statistical gaps: predictions using statistical physics, Port. Math. 75 (2018), 159–186

    2018

  4. [4]

    Kunisky, A

    D. Kunisky, A. S. Wein, and A. S. Bandeira,Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, inMathematical Analysis, its Applications and Computation (ISAAC 2019), Springer Proc. Math. Stat. 385, Springer, 2022, 1–50

    2019

  5. [5]

    Richard and A

    E. Richard and A. Montanari,A statistical model for tensor PCA, NeurIPS 2014, 2897–2905

    2014

  6. [6]

    A. S. Wein, A. El Alaoui, and C. Moore,The Kikuchi hierarchy and tensor PCA, J. ACM 72(5) (2025), Article 35; preliminary version in FOCS 2019

    2025

  7. [7]

    Kikuchi,A theory of cooperative phenomena, Phys

    R. Kikuchi,A theory of cooperative phenomena, Phys. Rev. 81 (1951), 988–1003

    1951

  8. [8]

    M. B. Hastings,Classical and quantum algorithms for tensor principal component analysis, Quantum 4 (2020), 237

    2020

  9. [9]

    Guruswami, P

    V. Guruswami, P. K. Kothari, and P. Manohar,Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random, STOC 2022, 678–689

    2022

  10. [10]

    Hsieh, P

    J.-T. Hsieh, P. K. Kothari, and S. Mohanty,A simple and sharper proof of the hypergraph Moore bound, SODA 2023, 2324–2344

    2023

  11. [11]

    Hsieh, P

    J.-T. Hsieh, P. K. Kothari, S. Mohanty, D. Munh´ a Correia, and B. Sudakov,Small even covers, locally decodable codes and restricted subgraphs of edge-colored Kikuchi graphs, Int. Math. Res. Not. 2025, no. 5, article rnaf045

    2025

  12. [12]

    Schmidhuber, R

    A. Schmidhuber, R. O’Donnell, R. Kothari, and R. Babbush,Quartic quantum speedups for planted inference, Phys. Rev. X 15 (2025), 021077; arXiv:2406.19378v2

    Pith/arXiv arXiv 2025

  13. [13]

    Schmidhuber and A

    A. Schmidhuber and A. Zlokapa,Quartic quantum speedups for community detection, arXiv:2510.08494

    arXiv

  14. [14]

    Alrabiah, V

    O. Alrabiah, V. Guruswami, P. K. Kothari, and P. Manohar,A near-cubic lower bound for 3-query locally decodable codes from semirandom CSP refutation, STOC 2023, 1438–1448

    2023

  15. [15]

    P. K. Kothari and P. Manohar,An exponential lower bound for linear 3-query locally correctable codes, STOC 2024, 776–787

    2024

  16. [16]

    S. B. Hopkins and D. Steurer,Efficient Bayesian estimation from few samples: community detection and related problems, FOCS 2017, 379–390

    2017

  17. [17]

    Feige,Small linear dependencies for binary vectors of low weight, inBuilding Bridges: Between Mathematics and Computer Science, Springer, 2008, 283–307

    U. Feige,Small linear dependencies for binary vectors of low weight, inBuilding Bridges: Between Mathematics and Computer Science, Springer, 2008, 283–307

    2008

  18. [18]

    Raghavendra, S

    P. Raghavendra, S. Rao, and T. Schramm,Strongly refuting random CSPs below the spectral threshold, STOC 2017, 121–131

    2017

  19. [19]

    d’Orsi and L

    T. d’Orsi and L. Trevisan,A Ihara–Bass formula for non-Boolean matrices and strong refutations of random CSPs, CCC 2023, LIPIcs 264, Article 27, 27:1–27:16

    2023

  20. [20]

    S. O. Chan, T. d’Orsi, and J. Xu,Strongly refuting random CSP without literals, arXiv:2604.27336 (2026). 55

    Pith/arXiv arXiv 2026

  21. [21]

    P. K. Kothari and J. Xu,Smooth trade-off for tensor PCA via sharp bounds for Kikuchi matrices, in Proceedings of the 2026 Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2026, 2617–2632, doi:10.1137/1.9781611978971.95

    work page doi:10.1137/1.9781611978971.95 2026

  22. [22]

    E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer,Decoding binary node labels from censored edge measurements: phase transition and efficient recovery, IEEE Trans. Netw. Sci. Eng. 1 (2014), 10–22

    2014

  23. [23]

    Hajek, Y

    B. Hajek, Y. Wu, and J. Xu,Achieving exact cluster recovery threshold via semidefinite programming: extensions, IEEE Trans. Inform. Theory 62 (2016), 5918–5937; arXiv:1502.07738

    Pith/arXiv arXiv 2016

  24. [24]

    K. Ahn, K. Lee, and C. Suh,Community recovery in hypergraphs, IEEE Trans. Inform. Theory 65 (2019), 6561–6579; arXiv:1709.03670

    Pith/arXiv arXiv 2019

  25. [25]

    A. S. Bandeira, D. Kunisky, P. Nizi´ c-Nikolac, L. Pesenti, and R. Wang,The hypergraph Moore bound, arXiv:2607.14068v2 (2026)

    Pith/arXiv arXiv 2026

  26. [26]

    Naor and J

    A. Naor and J. Verstra¨ ete,Parity check matrices and product representations of squares, Combinatorica 28 (2008), 163–185

    2008

  27. [27]

    J. A. Tropp,User-friendly tail bounds for sums of random matrices, Found. Comput. Math. 12 (2012), 389–434

    2012

  28. [28]

    Mao,Near optimal algorithms for noisyk-XOR under low-degree heuristic, arXiv:2604.10457 (2026)

    S. Mao,Near optimal algorithms for noisyk-XOR under low-degree heuristic, arXiv:2604.10457 (2026)

    Pith/arXiv arXiv 2026

  29. [29]

    Feige,Relations between average case complexity and approximation complexity, STOC 2002, 534–543

    U. Feige,Relations between average case complexity and approximation complexity, STOC 2002, 534–543

    2002

  30. [30]

    Coja-Oghlan, A

    A. Coja-Oghlan, A. Goerdt, and A. Lanka,Strong refutation heuristics for random k-SAT, Combin. Probab. Comput. 16 (2007), 5–28

    2007

  31. [31]

    S. R. Allen, R. O’Donnell, and D. Witmer,How to refute a random CSP, FOCS 2015, 689–708

    2015

  32. [32]

    Barak and A

    B. Barak and A. Moitra,Noisy tensor completion via the sum-of-squares hierarchy, COLT 2016, 417–445

    2016

  33. [33]

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

    D. Grigoriev,Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity, Theoret. Comput. Sci. 259 (2001), 613–622

    2001

  34. [34]

    Schoenebeck,Linear level Lasserre lower bounds for certaink-CSPs, FOCS 2008, 593–602

    G. Schoenebeck,Linear level Lasserre lower bounds for certaink-CSPs, FOCS 2008, 593–602

    2008

  35. [35]

    Alekhnovich and A

    M. Alekhnovich and A. A. Razborov,Lower bounds for polynomial calculus: non-binomial case, FOCS 2001, 190–199; expanded version, Proc. Steklov Inst. Math. 242 (2003), 18–35

    2001

  36. [36]

    O’Donnell and D

    R. O’Donnell and D. Witmer,Goldreich’s PRG: evidence for near-optimal polynomial stretch, CCC 2014, 1–12

    2014

  37. [37]

    Mori and D

    R. Mori and D. Witmer,Lower bounds for CSP refutation by SDP hierarchies, APPROX/RANDOM 2016, LIPIcs 60, 41:1–41:30; arXiv:1610.03029

    Pith/arXiv arXiv 2016

  38. [38]

    P. K. Kothari, R. Mori, R. O’Donnell, and D. Witmer,Sum of squares lower bounds for refuting any CSP, STOC 2017, 132–145

    2017

  39. [39]

    Basu, J.-T

    A. Basu, J.-T. Hsieh, A. D. Lin, and P. Manohar,Solving random planted CSPs below the nk/2 threshold, ICALP 2026; arXiv:2507.10833 (2025)

    Pith/arXiv arXiv 2026

  40. [40]

    P. K. Kothari,Kikuchi graphs of random hypergraphs are approximately Johnson, ECCC Report TR26-099; arXiv:2606.08597 (2026)

    Pith/arXiv arXiv 2026

  41. [41]

    Schramm and A

    T. Schramm and A. S. Wein,Computational barriers to estimation from low-degree polynomials, Ann. Statist. 50 (2022), 1833–1858

    2022

  42. [42]

    Alekhnovich,More on average case vs approximation complexity, FOCS 2003, 298–307

    M. Alekhnovich,More on average case vs approximation complexity, FOCS 2003, 298–307. 56

    2003

  43. [43]

    Barak, S

    B. Barak, S. B. Hopkins, J. Kelner, P. K. Kothari, A. Moitra, and A. Potechin,A nearly tight sum-of-squares lower bound for the planted clique problem, FOCS 2016, 428–437

    2016

  44. [44]

    S. B. Hopkins, P. K. Kothari, A. Potechin, P. Raghavendra, T. Schramm, and D. Steurer,The power of sum-of-squares for detecting hidden structures, FOCS 2017, 720–731

    2017

  45. [45]

    S. B. Hopkins,Statistical Inference and the Sum of Squares Method, Ph.D. thesis, Cornell University, 2018

    2018

  46. [46]

    A. Blum, A. Kalai, and H. Wasserman,Noise-tolerant learning, the parity problem, and the statistical query model, J. ACM 50 (2003), 506–519

    2003

  47. [47]

    Feldman, W

    V. Feldman, W. Perkins, and S. Vempala,On the complexity of random satisfiability problems with planted solutions, STOC 2015, 77–86

    2015

  48. [48]

    M. Xu, V. Jog, and P.-L. Loh,Optimal rates for community estimation in the weighted stochastic block model, Ann. Statist. 48 (2020), 183–204; arXiv:1706.01175

    Pith/arXiv arXiv 2020

  49. [49]

    Musco and C

    C. Musco and C. Musco,Randomized block Krylov methods for stronger and faster approximate singular value decomposition, NIPS 2015, 1396–1404

    2015

  50. [50]

    Kuczy´ nski and H

    J. Kuczy´ nski and H. Wo´ zniakowski,Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start, SIAM J. Matrix Anal. Appl. 13 (1992), 1094–1122

    1992

  51. [51]

    J. R. Bunch and L. Kaufman,Some stable methods for calculating inertia and solving symmetric linear systems, Math. Comp. 31 (1977), 163–179

    1977

  52. [52]

    E. H. Bareiss,Sylvester’s identity and multistep integer-preserving Gaussian elimination, Math. Comp. 22 (1968), 565–578

    1968

  53. [53]

    Holmgren and A

    J. Holmgren and A. S. Wein,Counterexamples to the low-degree conjecture, ITCS 2021, LIPIcs 185, article 75

    2021

  54. [54]

    Buhai, J.-T

    R.-D. Buhai, J.-T. Hsieh, A. Jain, and P. K. Kothari,The quasi-polynomial low-degree conjecture is false, FOCS 2025; arXiv:2505.17360

    Pith/arXiv arXiv 2025

  55. [55]

    Mao,The polynomial-time low-degree conjecture is false, arXiv:2607.20318 (2026)

    S. Mao,The polynomial-time low-degree conjecture is false, arXiv:2607.20318 (2026)

    Pith/arXiv arXiv 2026

  56. [56]

    Jia and A

    H. Jia and A. Vijayaraghavan,Low-degree method fails to predict robust subspace recovery, COLT 2026, PMLR 336, 3751–3781

    2026

  57. [57]

    Hsieh, D

    J.-T. Hsieh, D. M. Kane, P. K. Kothari, J. Li, S. Mohanty, and S. Tiegel,Rigorous implications of the low-degree heuristic, STOC 2026; arXiv:2601.05850

    arXiv 2026

  58. [58]

    Gupta, W

    M. Gupta, W. He, R. O’Donnell, and N. G. Singer,A classical quadratic speedup for planted kXOR, arXiv:2508.09422 (2025). 57

    Pith/arXiv arXiv 2025