Solving Random Planted CSPs below the $n^{k/2}$ Threshold

Andrew D. Lin; Arpon Basu; Jun-Ting Hsieh; Peter Manohar

REVIEW

Solving Random Planted CSPs below the $n^{k/2}$ Threshold

Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin, Peter Manohar

Data Structures and Algorithms · Submitted 14 Jul 2025 · 36 references

Pith's verdict: A genuinely new two-step algorithm that would close the planted-CSP search gap at the RRS17 trade-off, but the whole edifice rests on an unproven SoS-capture assertion that the authors themselves flag.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 6, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2507.10833 (version 1)

Pith IDLHY6NPH5, Pith's permanent record of this paper and its review

CitationAndrew D. Lin, Arpon Basu, Jun-Ting Hsieh, Peter Manohar. "Solving Random Planted CSPs below the $n^{k/2}$ Threshold." arXiv:2507.10833 (2025). https://pith.science/paper/LHY6NPH5

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The main event: this is the first search algorithm for random planted k-ary CSPs and noisy k-XOR at the conjectured optimal m ~ n(n/ℓ)^{k/2−1} constraint threshold in n^{O(ℓ)} time. The two-step plan—SoS approximate recovery followed by majority rounding from fresh constraints—is genuinely new and sidesteps the Kikuchi expansion barrier that blocked GHKM23 for super-constant ℓ. The proof of the rounding step (Lemma 5.2) is clean and the constant chasing in Lemmas 5.1, 5.4, and 5.5 looks careful. The paper also does a good job of saying where the field stood and what remains open; the semirandom gap is honestly flagged.

The soft spot is exactly where the stress-test puts it. Lemma 5.5 and Theorem 2 depend on Fact 3.8 being a degree-2ℓ SoS refutation. HKM23's theorem gives a spectral norm bound on the Kikuchi matrix, and the paper's Remark 3.9(2) asserts that this reasoning is 'straightforwardly' captured by degree-2ℓ SoS, with no proof. That is not a formality: a spectral bound controls a pseudo-expectation only through the second-moment route, and you need the trace-moment proof itself to be an SoS proof over the hypercube. If it uses matrix Chernoff or powers M^t with t > ℓ, the capture fails. Since the approximate-recovery step (Lemma 5.1) relies on Corollary 3.10, which inherits this gap, a failure there collapses the whole algorithm. The paper is honest enough to admit the missing proof, but it is load-bearing, not a side remark. The 'any hypergraph' wording of Fact 3.8 is also sloppy—HKM23 needs randomness/codegree conditions—though that is minor because the applications use random H.

Who gets value: anyone working on planted CSPs, sparse LPN, or the SoS / spectral gap. The result is important if the SoS capture is fixed, and the capture is plausibly provable from HKM23 or from known techniques. I would not cite the main theorems yet, but I would bring the paper to a reading group to dissect the capture question.

Recommendation: send to serious peer review, not desk reject. The constructive request to the authors is simple: either prove the degree-2ℓ SoS capture in full or point to a precise prior theorem with the proof supplied. That is an addressable gap, and the rest of the paper deserves referee time.

Referee report

Significance

If the SoS-capture issue is repaired, this is a substantial contribution: it gives the first search algorithm for random planted CSPs at the RRS17-style constraint/runtime trade-off, extending FPV15 from ell=O(1) to arbitrary ell. The two-step rounding idea is clean and likely to be influential. The paper is also careful in several places: it proves the necessary SoS rounding fact (Fact 3.7) in reasonable generality, it handles the even-k global-sign ambiguity explicitly, it gives precise statements about the list size in the CSP reduction, and it verifies concentration steps with Chernoff/McDiarmid. The main theorems are falsifiable and precisely stated, and the reduction from planted CSPs to noisy k-XOR is standard and appears correct. The weakness is not in the internal logic once Fact 3.8 is granted; it is in the unsupported bridge between a known spectral-norm refutation algorithm and a degree-2ell SoS refutation certificate.

Major objections (2)

[Section 3.2, Fact 3.8 and Remark 3.9(2)] The central claim that degree-2ell SoS refutes random k-XOR at the stated density is not proved. Fact 3.8 cites HKM23 Theorem 4.1, but Remark 3.9(2) explicitly concedes that the formal statement of that theorem gives a spectral-norm bound on the level-ell Kikuchi matrix, not a degree-2ell SoS certificate. The assertion that this reasoning is 'straightforwardly' captured by degree-2ell SoS is load-bearing: Corollary 3.10, Lemma 5.5, Lemma 5.4, and Lemma 5.1 all use it. A spectral-norm bound controls eE[psi] only if the trace-moment argument is itself a degree-2ell SoS proof over the hypercube; if HKM23's proof uses powers M^t with t > ell or matrix Chernoff/randomized-rounding steps, no degree-2ell certificate follows. Please provide a full proof of Fact 3.8, or replace it with an exact citation to a theorem that gives the SoS certificate, or state and prove a restricted version sufficient for Corollary 3.10.
[Section 3.2, Fact 3.8] Fact 3.8 is stated for 'any hypergraph H' with |H| at least the stated threshold. This is broader than what the cited HKM23 theorem supports if that theorem requires randomness or codegree structure in H; as stated, the fact is not a direct consequence of the citation. The applications in Corollary 3.10 and later only need H to be a uniform random sample from [n]^k, so the over-broad statement is not fatal to the main theorems, but it should be corrected: restate Fact 3.8 with the precise hypotheses under which it is true and proved, and derive the random-H version explicitly.

Minor objections (4)

[Appendix A] The appendix title 'Auxilliary Statements' contains a typo; it should be 'Auxiliary Statements'.
[Algorithm 3, Step (2iii)] The quantity delta_i is not formally defined. It should be defined as the infimum over delta >= 0 such that |corr(bx^(i), bx^(j))| >= 1 - delta for at least 0.99n choices of j, so that the subsequent minimization over i is unambiguous.
[Lemma 5.2] The symbol ex is used both for the input approximate assignment and for the output exact assignment in the statement of Lemma 5.2. Rename the input, e.g., to bx, as is done in the proof, to avoid confusion.
[Fact 3.6] Fact 3.6 states an additive error of 4^{-n} for the computed moments and then concludes an error of 2^{-n} for the objective value. Please reconcile these constants, since the error for a general polynomial f should depend on the number of monomials in f.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Random planted CSPs solved at the refutation trade-off: an n^{O(ℓ)}-time algorithm recovers a satisfying assignment whenever m ≥ O(n log n)(n/ℓ)^{k/2−1}, matching the known refutation thresholds.

The reading

This paper claims that random planted instances of any k-ary Boolean constraint satisfaction problem can be solved much more flexibly than before: for any runtime exponent ℓ, an algorithm running in $n^{{O(ℓ)}}$ time returns a satisfying assignment as long as the instance has about O(n log n)(n/ℓ)^{k/2−1} constraints. That is the same constraint-versus-runtime trade-off that was already known for refuting random CSPs, so the paper closes the search side of that gap. The key move is to abandon uniqueness certificates: first a degree-2ℓ sum-of-squares relaxation finds an assignment close to the planted one, and then fresh constraints round it to an exact solution. If correct, this also gives new algorithms for noisy k-XOR (k-sparse LPN) and for inverting Goldreich-style pseudorandom generators.

What carries the argument

The load-bearing object is the degree-2ℓ sum-of-squares pseudoexpectation over the Boolean hypercube. For an XOR system with right-hand sides b_C, the algorithm forms ψ(x) = E_{C∼H}[b_C x_C] and computes a pseudoexpectation µ maximizing Ẽ_µ[ψ(x)]. Two sum-of-squares-certifiable facts do the work: Fact 3.8 (the known spectral refutation of random k-XOR, asserted to be captured by degree-2ℓ SoS) bounds Ẽ[Σ σ_C x_C] for Rademacher signs σ_C, and Lemma 5.5 uses a symmetrization argument with Rademacher signs to show that a random sample of hyperedges behaves like the complete hypergraph, forcing Ẽ[E_{C∼H}[x_C]] ≈ (1/n^k)Ẽ[⟨x,x*⟩^k]. Together these give Ẽ[⟨x,x*⟩^k] ≈ n^k, and Fact 3.7 converts that large moment into a correlated vector: the sign of Ẽ[x] for odd k, or a row of Ẽ[$x^{{⊗2}}$] for even k. The second rounding step, Algorithm 4, observes that if the approximate assignment differs from x* on o(n) coordinates, then most constraints through a fixed coordinate contain only correct coordinates, so the majority of b_C times the product over the other coordinates equals that coordinate of x*.

Extended reading notes

Core claim

The central claim is Theorem 1: for a random planted k-ary Boolean CSP whose planting distribution has complexity r, an $n^{{O(ℓ)}}$-time algorithm outputs a list of at most $2^{{k+2}}$ assignments, at least one of which satisfies the instance, provided m ≥ $2^{{O(k)}}$ n log n (n/ℓ)^{r/2−1}. This is proved through Theorem 2, a new algorithm for noisy k-XOR that recovers the planted assignment exactly, up to a global sign when k is even, provided m ≥ $2^{{O(k)}}$ n log n max($ε^{{-11}}$(n/ℓ)^{k/2−1}, $ε^{{-2}}$) and ε²/k ≥ Ω($n^{{-1/2}}$). The algorithm works in two independent steps: it first maximizes the canonical degree-2ℓ sum-of-squares relaxation of the XOR system to obtain an assignment with correlation 1−o(1) with the planted one, then rounds that approximate assignment by a majority vote over freshly used constraints, exploiting that a nearly correct assignment makes most constraints through a given coordinate reveal that coordinate's planted sign.

Load-bearing premise

The entire reduction leans on the assertion, stated in Remark 3.9(2) without a proof, that the known spectral refutation of random k-XOR is captured by a degree-2ℓ sum-of-squares proof even when ℓ grows with n; if that capture fails, Lemma 5.5 and the approximate-recovery step collapse.

Editorial extensions

If this is right

If Theorem 1 is correct, every random planted k-ary CSP is solvable in time n^{O(ℓ)} at the same constraint density at which random CSPs are refutable, removing the search/refutation gap for the random planted model.
Theorems 1 and 2 give new inversion algorithms for Goldreich-style pseudorandom generators and for k-sparse LPN in the high-noise regime, for stretches and noise levels obeying the stated trade-off.
For even k, the paper notes the noisy-XOR threshold can be improved from ε^{-11} to ε^{-7}, so even fewer constraints suffice as the noise parameter ε grows.
When the planting distribution is known to the algorithm, the list of 2^{k+2} candidates collapses to exact recovery of x* up to a global sign, matching the earlier polynomial-time guarantee without the runtime restriction.
The two-step structure interpolates smoothly between polynomial time at ℓ = O(1) and near-linear constraint counts at ℓ ≈ n, giving a full family of algorithms rather than a single threshold result.

Reading between the lines

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

Inference: The semirandom planted-CSP search problem, where scopes are chosen adversarially, remains open; the same two-step design would solve it if a degree-2ℓ sum-of-squares refutation existed for semirandom k-XOR, making that the natural next target.
Inference: The paper's reliance on Remark 3.9(2) suggests a direct litmus test: produce an actual degree-2ℓ SoS certificate for the spectral refutation at ℓ = ω(1). If the capture assertion is false, the approximate-recovery lemma fails before any rounding issue arises.
Inference: The algorithm could likely be made more economical by reusing the same constraints for both the SoS step and the majority rounding step rather than splitting the instance in half, at the cost of a more delicate correlation analysis.
Inference: When Q is unknown, the list of candidate assignments could perhaps be reduced to exact recovery by a consistency post-filter among the candidates, rather than by knowing the planting distribution, yielding a stronger statement than the list guarantee.

Original abstract

We present a family of algorithms to solve random planted instances of any $k$-ary Boolean constraint satisfaction problem (CSP). A randomly planted instance of a Boolean CSP is generated by (1) choosing an arbitrary planted assignment $x^*$, and then (2) sampling constraints from a particular "planting distribution" designed so that $x^*$ will satisfy every constraint. Given an $n$ variable instance of a $k$-ary Boolean CSP with $m$ constraints, our algorithm runs in time $n^{O(\ell)}$ for a choice of a parameter $\ell$, and succeeds in outputting a satisfying assignment if $m \geq O(n) \cdot (n/\ell)^{\frac{k}{2} - 1} \log n$. This generalizes the $\mathrm{poly}(n)$-time algorithm of [FPV15], the case of $\ell = O(1)$, to larger runtimes, and matches the constraint number vs.\ runtime trade-off established for refuting random CSPs by [RRS17]. Our algorithm is conceptually different from the recent algorithm of [GHKM23], which gave a $\mathrm{poly}(n)$-time algorithm to solve semirandom CSPs with $m \geq \tilde{O}(n^{\frac{k}{2}})$ constraints by exploiting conditions that allow a basic SDP to recover the planted assignment $x^*$ exactly. Instead, we forego certificates of uniqueness and recover $x^*$ in two steps: we first use a degree-$O(\ell)$ Sum-of-Squares SDP to find some $\hat{x}$ that is $o(1)$-close to $x^*$, and then we use a second rounding procedure to recover $x^*$ from $\hat{x}$.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 5,519 input tokens.

What the abstract itself states, as probabilities: claims first 0.07 · states limitation 0.34 · human participants 0.01 · controlled comparison 0.07 · randomized assignment 0.46 · states quantitative result 0.98 · compares with prior results 0.98 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

We present a family of algorithms to solve random planted instances of any $k$-ary Boolean constraint satisfaction problem (CSP). A randomly planted instance of a Boolean CSP is generated by (1) choosing an arbitrary planted assignment $x^*$, and then (2) sampling constraints from a particular "planting distribution" designed so that $x^*$ will satisfy every constraint. Given an $n$ variable instance of a $k$-ary Boolean CSP with $m$ constraints, our algorithm runs in time $n^{O(\ell)}$ for a choice of a parameter $\ell$, and succeeds in outputting a satisfying assignment if $m \geq O(n) \cdot (n/\ell)^{\frac{k}{2} - 1} \log n$. This generalizes the $\mathrm{poly}(n)$-time algorithm of [FPV15], the case of $\ell = O(1)$, to larger runtimes, and matches the constraint number vs.\ runtime trade-off established for refuting random CSPs by [RRS17]. Our algorithm is conceptually different from the recent algorithm of [GHKM23], which gave a $\mathrm{poly}(n)$-time algorithm to solve semirandom CSPs with $m \geq \tilde{O}(n^{\frac{k}{2}})$ constraints by exploiting conditions that allow a basic SDP to recover the planted assignment $x^*$ exactly. Instead, we forego certificates of uniqueness and recover $x^*$ in two steps: we first use a degree-$O(\ell)$ Sum-of-Squares SDP to find some $\hat{x}$ that is $o(1)$-close to $x^*$, and then we use a second rounding procedure to recover $x^*$ from $\hat{x}$.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	We present a family of algorithms to solve random planted instances of any $k$-ary Boolean constraint satisfaction problem (CSP).	contribution 1.00	0.95	0.39	asserted 1.00
s1	A randomly planted instance of a Boolean CSP is generated by (1) choosing an arbitrary planted assignment $x^$, and then (2) sampling constraints from a particular "planting distribution" designed so that $x^$ will satisfy every constraint.	background 0.96	0.12	0.03	asserted 0.99
s2	Given an $n$ variable instance of a $k$-ary Boolean CSP with $m$ constraints, our algorithm runs in time $n^{O(\ell)}$ for a choice of a parameter $\ell$, and succeeds in outputting a satisfying assignment if $m \geq O(n) \cdot (n/\ell)^{\frac{k}{2} - 1} \log n$.	result 0.75	0.95	0.62	asserted 1.00
s3	This generalizes the $\mathrm{poly}(n)$-time algorithm of [FPV15], the case of $\ell = O(1)$, to larger runtimes, and matches the constraint number vs.\ runtime trade-off established for refuting random CSPs by [RRS17].	interpretation 0.79	0.51	0.17	asserted 1.00
s4	Our algorithm is conceptually different from the recent algorithm of [GHKM23], which gave a $\mathrm{poly}(n)$-time algorithm to solve semirandom CSPs with $m \geq \tilde{O}(n^{\frac{k}{2}})$ constraints by exploiting conditions that allow a basic SDP to recover the planted assignment $x^*$ exactly.	background 0.59	0.17	0.06	asserted 1.00
s5	Instead, we forego certificates of uniqueness and recover $x^$ in two steps: we first use a degree-$O(\ell)$ Sum-of-Squares SDP to find some $\hat{x}$ that is $o(1)$-close to $x^$, and then we use a second rounding procedure to recover $x^*$ from $\hat{x}$.	method 0.99	0.94	0.14	asserted 1.00

What kind of paper the classifier reports this is: method or tool 0.94 · evidence from proof or derivation 0.98.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Works cited (36)

[1]

Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 , pages 171--180. ACM , 2010

View on Pith 2010
[2]

Jackson Abascal, Venkatesan Guruswami, and Pravesh K. Kothari. Strongly refuting all semi-random Boolean CSPs . In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021 , pages 454--472. SIAM , 2021

View on Pith 2021
[3]

Sanjeev Arora, David R. Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems . In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA , pages 284--293. ACM , 1995

View on Pith 1995
[4]

Michael Alekhnovich. More on average case vs approximation complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 11-14 October 2003, Cambridge, MA, USA . IEEE , 2003

View on Pith 2003
[5]

Sarah R. Allen, Ryan O'Donnell, and David Witmer. How to Refute a Random CSP . In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015 , pages 689--708. IEEE Computer Society, 2015

View on Pith 2015
[6]

Benny Applebaum. Cryptographic Hardness of Random Local Functions: Survey . Computational complexity , 25:667--722, 2016

View on Pith 2016
[7]

Boaz Barak, Siu On Chan, and Pravesh K. Kothari. Sum of Squares Lower Bounds from Pairwise Independence . In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 , pages 97--106. ACM , 2015

View on Pith 2015
[8]

Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani. SDP gaps from pairwise independence . Theory of Computing , 8(1):269--289, 2012

View on Pith 2012
[9]

Wolfgang Barthel, Alexander K Hartmann, Michele Leone, Federico Ricci-Tersenghi, Martin Weigt, and Riccardo Zecchina. Hiding solutions in random satisfiability problems: A statistical mechanics approach . Physical review letters , 88(18):188701, 2002

View on Pith 2002
[10]

Boaz Barak and Ankur Moitra. Noisy Tensor Completion via the Sum-of-Squares Hierarchy . In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016 , volume 49 of JMLR Workshop and Conference Proceedings , pages 417--445. JMLR.org, 2016

View on Pith 2016
[11]

Andrej Bogdanov and Youming Qiao. On the security of Goldreich's one-way function . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 12th International Workshop, APPROX 2009 , pages 392--405. Springer, 2009

View on Pith 2009
[12]

Boaz Barak and David Steurer. Proofs, beliefs, and algorithms through the lens of sum-of-squares, 2016. Lecture notes in preparation, available on http://sumofsquares.org

View on Pith 2016
[13]

Amin Coja - Oghlan, Colin Cooper, and Alan Frieze. An efficient sparse regularity concept . SIAM Journal on Discrete Mathematics , 23(4):2000--2034, 2010

View on Pith 2000
[14]

Amin Coja - Oghlan, Andreas Goerdt, and Andr \'e Lanka. Strong refutation heuristics for random k -SAT . Combinatorics, Probability & Computing , 16(1):5, 2007

View on Pith 2007
[15]

Xue Chen, Wenxuan Shu, and Zhaienhe Zhou. Algorithms for Sparse LPN and LSPN Against Low-noise . In 38th Annual Conference on Learning Theory (COLT 2025) . Association for Computational Learning (ACL), 2025

View on Pith 2025
[16]

Uriel Feige. Relations between average case complexity and approximation complexity . In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages 534--543, 2002

View on Pith 2002
[17]

Noah Fleming, Pravesh Kothari, and Toniann Pitassi. Semialgebraic Proofs and Efficient Algorithm Design . Foundations and Trends in Theoretical Computer Science , 14(1-2):1--221, 2019

View on Pith 2019
[18]

Dimitris Fotakis, Michael Lampis, and Vangelis Th. Paschos. Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse . In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orl \' e ans, France , volume 47 of LIPIcs , pages 37:1--37:14. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2016

View on Pith 2016
[19]

Vitaly Feldman, Will Perkins, and Santosh S. Vempala. Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's . In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada , pages 2836--2844, 2015

View on Pith 2015
[20]

Vitaly Feldman, Will Perkins, and Santosh S. Vempala. On the Complexity of Random Satisfiability Problems with Planted Solutions . SIAM Journal on Computing , 47(4):1294--1338, 2018

View on Pith 2018
[21]

Venkatesan Guruswami, Jun - Ting Hsieh, Pravesh K. Kothari, and Peter Manohar. Efficient algorithms for semirandom planted csps at the refutation threshold. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023 , pages 307--327. IEEE , 2023

View on Pith 2023
[22]

Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random . In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 , pages 678--689. ACM , 2022

View on Pith 2022
[23]

Andreas Goerdt and Andr \' e Lanka. Recognizing more random unsatisfiable 3-sat instances efficiently. Electron. Notes Discret. Math. , 16:21--46, 2003

View on Pith 2003
[24]

Oded Goldreich. Candidate One-Way Functions Based on Expander Graphs . Electron. Colloquium Comput. Complex. , 2000

View on Pith 2000
[25]

Johan H stad. Some optimal inapproximability results . Journal of the ACM (JACM) , 48(4):798--859, 2001

View on Pith 2001
[26]

Jun - Ting Hsieh, Pravesh K. Kothari, and Sidhanth Mohanty. A simple and sharper proof of the hypergraph Moore bound . In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 , pages 2324--2344. SIAM , 2023

View on Pith 2023
[27]

Samuel B. Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-square proofs. In Proceedings of The 28th Conference on Learning Theory , volume 40 of Proceedings of Machine Learning Research , pages 956--1006, Paris, France, 03--06 Jul 2015. PMLR

View on Pith 2015
[28]

Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT . J. Comput. Syst. Sci. , 62(2):367--375, 2001

View on Pith 2001
[29]

Haixia Jia, Cristopher Moore, and Doug Strain. Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively . Journal of Artificial Intelligence Research , 28:107--118, 2007

View on Pith 2007
[30]

Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP . In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 , pages 132--145. ACM , 2017

View on Pith 2017
[31]

Colin McDiarmid. On the method of bounded differences. In Surveys in combinatorics, 1989 ( N orwich, 1989) , volume 141 of London Math. Soc. Lecture Note Ser. , pages 148--188. Cambridge Univ. Press, Cambridge, 1989

View on Pith 1989
[32]

Ryuhei Mori and David Witmer. Lower Bounds for CSP Refutation by SDP Hierarchies . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France , volume 60 of LIPIcs , pages 41:1--41:30, 2016

View on Pith 2016
[33]

Ryan O'Donnell and David Witmer. Goldreich's PRG: evidence for near-optimal polynomial stretch . In 2014 IEEE 29th Conference on Computational Complexity (CCC) , pages 1--12. IEEE, 2014

View on Pith 2014
[34]

Ryan O'Donnell and Yuan Zhou. Approximability and proof complexity. In Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1537--1556, 2013

View on Pith 2013
[35]

Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random CSPs below the spectral threshold . In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 , pages 121--131. ACM , 2017

View on Pith 2017
[36]

Alexander S. Wein, Ahmed El Alaoui, and Cristopher Moore. The Kikuchi Hierarchy and Tensor PCA . In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019 , pages 1446--1468. IEEE Computer Society, 2019

View on Pith 2019

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

The Kikuchi Hierarchy is Sharp for $k$XOR
cs.DS 2026-07 conditional novelty 8.0 of 10

Normalized Kikuchi matrices achieve the sharp m ~ rho^{-2} n^{k/2} / ell^{k/2-1} trade-off with no logarithmic loss for detection, recovery, and two-sided refutation in kXOR, with matching low-degree lower bounds.
Sharp Bounds on Ground State Energy of the SYK Model
quant-ph 2026-07 accept novelty 7.5 of 10

For super-constant k = o(√n), the expected operator norm of the k-SYK Hamiltonian equals (1−o(1))√(2n)/k, via a twisted-boson operator whose moments match SYK trace moments exactly.
Sum-of-Squares Refutation Implies Planted Recovery for Semirandom CSPs
cs.DS 2026-11 conditional novelty 7.0 of 10

SoS refutation certificates for semirandom k-XOR are converted, via a learned decomposition and a sample-splitting voting trick, into an n^{O(ell)}-time algorithm recovering planted solutions to semirandom Boolean CSP...

How the literature uses it

4 arXiv papers cite this in 9 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 3 sentences without a confident label

Compares with it 2 papers

Our result substantially improves the dependence on the bias parameter over the previous best recovery algorithm of Basu et al. [ref] , achieving the information-theoretically optimal $δ^-2$ scaling.

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic · Introduction · 1.00
An algorithm with similar density running time trade-off was recently obtained by [ref] .

Kikuchi Graphs of Random Hypergraphs are Approximately Johnson · Application to Solving Planted $2r$-XOR · 0.93

Cites it as background 2 papers

More recently, Basu et al. [ref] obtained a new algorithm for the search version of noisy $k$-XOR.

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic · Introduction · 0.89
This includes hardness and cryptographic formulations of sparse noisy parity/$k$-LIN/XOR-code problems [ref] , as well as algorithmic work on planted and random CSPs [ref] .

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR · Statistical-Computational Gap and Expansion Properties · 0.99

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 , pages 171--180. ACM , 2010

View on Pith 2010

[2] [2]

Jackson Abascal, Venkatesan Guruswami, and Pravesh K. Kothari. Strongly refuting all semi-random Boolean CSPs . In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021 , pages 454--472. SIAM , 2021

View on Pith 2021

[3] [3]

Sanjeev Arora, David R. Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems . In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA , pages 284--293. ACM , 1995

View on Pith 1995

[4] [4]

Michael Alekhnovich. More on average case vs approximation complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 11-14 October 2003, Cambridge, MA, USA . IEEE , 2003

View on Pith 2003

[5] [5]

Sarah R. Allen, Ryan O'Donnell, and David Witmer. How to Refute a Random CSP . In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015 , pages 689--708. IEEE Computer Society, 2015

View on Pith 2015

[6] [6]

Benny Applebaum. Cryptographic Hardness of Random Local Functions: Survey . Computational complexity , 25:667--722, 2016

View on Pith 2016

[7] [7]

Boaz Barak, Siu On Chan, and Pravesh K. Kothari. Sum of Squares Lower Bounds from Pairwise Independence . In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 , pages 97--106. ACM , 2015

View on Pith 2015

[8] [8]

Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani. SDP gaps from pairwise independence . Theory of Computing , 8(1):269--289, 2012

View on Pith 2012

[9] [9]

Wolfgang Barthel, Alexander K Hartmann, Michele Leone, Federico Ricci-Tersenghi, Martin Weigt, and Riccardo Zecchina. Hiding solutions in random satisfiability problems: A statistical mechanics approach . Physical review letters , 88(18):188701, 2002

View on Pith 2002

[10] [10]

Boaz Barak and Ankur Moitra. Noisy Tensor Completion via the Sum-of-Squares Hierarchy . In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016 , volume 49 of JMLR Workshop and Conference Proceedings , pages 417--445. JMLR.org, 2016

View on Pith 2016

[11] [11]

Andrej Bogdanov and Youming Qiao. On the security of Goldreich's one-way function . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 12th International Workshop, APPROX 2009 , pages 392--405. Springer, 2009

View on Pith 2009

[12] [12]

Boaz Barak and David Steurer. Proofs, beliefs, and algorithms through the lens of sum-of-squares, 2016. Lecture notes in preparation, available on http://sumofsquares.org

View on Pith 2016

[13] [13]

Amin Coja - Oghlan, Colin Cooper, and Alan Frieze. An efficient sparse regularity concept . SIAM Journal on Discrete Mathematics , 23(4):2000--2034, 2010

View on Pith 2000

[14] [14]

Amin Coja - Oghlan, Andreas Goerdt, and Andr \'e Lanka. Strong refutation heuristics for random k -SAT . Combinatorics, Probability & Computing , 16(1):5, 2007

View on Pith 2007

[15] [15]

Xue Chen, Wenxuan Shu, and Zhaienhe Zhou. Algorithms for Sparse LPN and LSPN Against Low-noise . In 38th Annual Conference on Learning Theory (COLT 2025) . Association for Computational Learning (ACL), 2025

View on Pith 2025

[16] [16]

Uriel Feige. Relations between average case complexity and approximation complexity . In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages 534--543, 2002

View on Pith 2002

[17] [17]

Noah Fleming, Pravesh Kothari, and Toniann Pitassi. Semialgebraic Proofs and Efficient Algorithm Design . Foundations and Trends in Theoretical Computer Science , 14(1-2):1--221, 2019

View on Pith 2019

[18] [18]

Dimitris Fotakis, Michael Lampis, and Vangelis Th. Paschos. Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse . In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orl \' e ans, France , volume 47 of LIPIcs , pages 37:1--37:14. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2016

View on Pith 2016

[19] [19]

Vitaly Feldman, Will Perkins, and Santosh S. Vempala. Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's . In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada , pages 2836--2844, 2015

View on Pith 2015

[20] [20]

Vitaly Feldman, Will Perkins, and Santosh S. Vempala. On the Complexity of Random Satisfiability Problems with Planted Solutions . SIAM Journal on Computing , 47(4):1294--1338, 2018

View on Pith 2018

[21] [21]

Venkatesan Guruswami, Jun - Ting Hsieh, Pravesh K. Kothari, and Peter Manohar. Efficient algorithms for semirandom planted csps at the refutation threshold. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023 , pages 307--327. IEEE , 2023

View on Pith 2023

[22] [22]

Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random . In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 , pages 678--689. ACM , 2022

View on Pith 2022

[23] [23]

Andreas Goerdt and Andr \' e Lanka. Recognizing more random unsatisfiable 3-sat instances efficiently. Electron. Notes Discret. Math. , 16:21--46, 2003

View on Pith 2003

[24] [24]

Oded Goldreich. Candidate One-Way Functions Based on Expander Graphs . Electron. Colloquium Comput. Complex. , 2000

View on Pith 2000

[25] [25]

Johan H stad. Some optimal inapproximability results . Journal of the ACM (JACM) , 48(4):798--859, 2001

View on Pith 2001

[26] [26]

Jun - Ting Hsieh, Pravesh K. Kothari, and Sidhanth Mohanty. A simple and sharper proof of the hypergraph Moore bound . In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 , pages 2324--2344. SIAM , 2023

View on Pith 2023

[27] [27]

Samuel B. Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-square proofs. In Proceedings of The 28th Conference on Learning Theory , volume 40 of Proceedings of Machine Learning Research , pages 956--1006, Paris, France, 03--06 Jul 2015. PMLR

View on Pith 2015

[28] [28]

Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT . J. Comput. Syst. Sci. , 62(2):367--375, 2001

View on Pith 2001

[29] [29]

Haixia Jia, Cristopher Moore, and Doug Strain. Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively . Journal of Artificial Intelligence Research , 28:107--118, 2007

View on Pith 2007

[30] [30]

Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP . In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 , pages 132--145. ACM , 2017

View on Pith 2017

[31] [31]

Colin McDiarmid. On the method of bounded differences. In Surveys in combinatorics, 1989 ( N orwich, 1989) , volume 141 of London Math. Soc. Lecture Note Ser. , pages 148--188. Cambridge Univ. Press, Cambridge, 1989

View on Pith 1989

[32] [32]

Ryuhei Mori and David Witmer. Lower Bounds for CSP Refutation by SDP Hierarchies . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France , volume 60 of LIPIcs , pages 41:1--41:30, 2016

View on Pith 2016

[33] [33]

Ryan O'Donnell and David Witmer. Goldreich's PRG: evidence for near-optimal polynomial stretch . In 2014 IEEE 29th Conference on Computational Complexity (CCC) , pages 1--12. IEEE, 2014

View on Pith 2014

[34] [34]

Ryan O'Donnell and Yuan Zhou. Approximability and proof complexity. In Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1537--1556, 2013

View on Pith 2013

[35] [35]

Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random CSPs below the spectral threshold . In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 , pages 121--131. ACM , 2017

View on Pith 2017

[36] [36]

Alexander S. Wein, Ahmed El Alaoui, and Cristopher Moore. The Kikuchi Hierarchy and Tensor PCA . In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019 , pages 1446--1468. IEEE Computer Society, 2019

View on Pith 2019