Sum-of-Squares Refutation Implies Planted Recovery for Semirandom CSPs

Andrew D. Lin; Arpon Basu; Peter Manohar

REVIEW

Sum-of-Squares Refutation Implies Planted Recovery for Semirandom CSPs

Arpon Basu, Andrew D. Lin, Peter Manohar

Data Structures and Algorithms · Submitted 5 Nov 2026 · 36 references

Pith's verdict: A genuinely new search-to-refutation reduction for semirandom planted CSPs; the main proof checks out, with one patchable gap and an honest AI-use disclosure.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on November 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 · 5 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2611.08114 (version 1)

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

CitationAndrew D. Lin, Arpon Basu, Peter Manohar. "Sum-of-Squares Refutation Implies Planted Recovery for Semirandom CSPs." arXiv:2611.08114 (2026). https://pith.science/paper/FHI3K32G

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

Bottom line: this is the real thing. The paper gives the first search-to-refutation reduction for semirandom CSPs, and the learning-the-bad-hyperedges approach is genuinely new. The theorem is conditional on degree-2ℓ SoS refutation of semirandom k-XOR on the same hypergraph, but that condition is explicit and it is instantiated unconditionally with the HKM23 bound in the corollaries. The resulting algorithm matches the (n/ℓ)^{k/2}ℓ polylog(n) threshold in n^{O(ℓ)} time, closing the gap left by GHKM23, BHLM26, and Kot26. I checked the error accounting in Lemmas 3.5 and 3.6 and the main estimates are coherent. There is a small formal wrinkle: the proof of Lemma 3.5 bounds E|Σσ_C| by n, which needs an unstated m ≥ Ω(n/(ε̂γ)); replacing it by √m fixes the line, and the corollary thresholds already dominate that lower bound. That is hygiene, not a flaw in the central claim.

The reduction itself is the contribution. Previous semirandom planted work decomposed the hypergraph by expansion or Johnson sparsification, and the paper explains why those properties are too strong. Here the algorithm learns a large set of good hyperedges by running the predictor on synthetic samples and then uses the sample-splitting lemma to convert one planted sample into many lower-bias samples. The proof that the predictor makes few expected mistakes is clean and uses the refutation certificate as intended.

Soft spots, in order. First, the sample-splitting lemma is acknowledged to be a known cloning result from BB20/BB19; the AI-use statement says GPT-6 Astra supplied it, likely from those papers. This does not hurt correctness because the proof is self-contained and the citations are now in Remark 3.9, but it moves the novelty to the framework and Lemma 3.5. Second, the abstract's "up to polylog" is doing a bit of work: the corollaries carry ε^{-4} and γ^{-4} factors, which are constants for fixed noise and accuracy but not if those parameters shrink with n. Worth a wording fix. Third, no machine-checked proofs or code, so my confidence is from reading, not verification.

On balance I would send this to a serious referee. The conditional nature of Theorem 3.1 is stated, not hidden, and the conditional is the honest form of the result. The paper deserves referee time; the referee should ask for the Lemma 3.5 fix and a sharper statement of parameter dependence.

What would settle it

Generate $\Phi \sim \mathrm{XOR}(\mathcal{H}, 1^n, 0)$ on a specific hypergraph $\mathcal{H}$, solve the degree-$2\ell$ Sum-of-Squares SDP, and record whether the certificate bound $1/2 + \gamma\hat{\varepsilon}/(720\log(mn))$ holds. Then plant a known $x^*$ with known $\varepsilon$ on the same $\mathcal{H}$, run the full pipeline (Predict, Prune, sample splitting, majority vote) on $\Psi \sim \mathrm{XOR}(\mathcal{H}, x^*, \varepsilon)$, and count mislabelled kept hyperedges and the size of $\mathcal{H}_0$. The theorem predicts zero mislabelled kept edges and $|\mathcal{H}_0| \le \gamma m$ whenever the certificate holds and $|\hat{\varepsilon} - \varepsilon|$ is small. Exhibiting one $\mathcal{H}$ where the certificate's slack is numerically verified but mislabelled kept edges occur with non-negligible probability would refute the reduction, while running the same test below the $m \gtrsim (n/\ell)^{k/2}\,\ell$ threshold, where the certificate is known to fail, tests whether the hypothesis is also necessary.

Referee report

Significance

If the proof gaps noted below are repaired, this is a significant conceptual contribution: it is, to my knowledge, the first explicit search-to-refutation reduction for semirandom CSPs, and it correctly identifies the conditional hypothesis as refutability of the random-sign instance on the worst-case hypergraph rather than an explicit expansion or pseudorandomness decomposition. The conditional nature of Theorem 3.1 is stated honestly and is not hidden; the corollaries are grounded in a published refutation bound (Fact 2.4) rather than fitted to the target. The sample-splitting lemma is proved in a self-contained way, and the authors explicitly acknowledge that it follows from the known cloning results [BBH19, BB20]. The high-level idea of learning the set of bad hyperedges is a genuine departure from the decomposition blueprint of prior work.

Major objections (2)

[Section 3.1, proof of Lemma 3.5] The display ending in "2ε̂γm/9 + 2n ≤ 3ε̂γm/13" is not justified under the stated hypotheses. The sum of Rademacher variables has E|Σ_{C∈H} σ_C| ≤ √m, not ≤ n, and the implied lower bound m ≥ Ω(n/(ε̂γ)) (with an explicit constant 234) appears neither in Lemma 3.5 nor in Theorem 3.1. As printed, therefore, the claim that the expected number of mistakes is at most 3γm/13 is not proved for the stated range of m. The proof can be repaired locally: either use E[Σ σ_C] = 0 to remove the extra term, or keep 2E|Σ σ_C| and bound it by 2√m, which introduces an additional condition m ≥ Ω((ε̂γ)^{-2}) that should be stated in Theorem 3.1. The thresholds in Corollaries 3.2 and 3.4 automatically satisfy such a condition, so the main trade-off is not endangered, but the theorem as stated is not fully proved.
[Section 3, proof of Theorem 3.1 and statement of Lemma 3.5] The application of Lemma 3.5 is underspecified and on a literal reading has a parameter mismatch. Lemma 3.5 is stated under the hypothesis max_{eE∈SoS_{2ℓ}} eE[Φ] ≤ 1/2 + ε̂γ/18 with the same ε̂, whereas Theorem 3.1 supplies only the bound 1/2 + γ ε̂/(720 log(mn)). The proof sets t = 20 log(mn) and correctly uses ε̂/(2t) for Predict, but then says "Run the algorithm Prune from Lemma 3.5 on H" without specifying the bias parameter, and Algorithm 3.8 declares only H as input while its operation samples from Bias(ε̂). The proof goes through if Prune is also run with ε̂/(2t), because the lemma's hypothesis then becomes exactly 1/2 + γε̂/(720 log(mn)). Please make that call, and the input specification of Prune, explicit.

Minor objections (5)

[Section 3.1, Algorithm 3.7] Step (2) writes the SDP objective as eE[∏_{C∈H} ζ_C x_C]; the product has total degree km and cannot be evaluated by a degree-2ℓ pseudo-expectation when km > 2ℓ. The surrounding proof and all subsequent displays use the sum ∑_{C∈H} ζ_C x_C, so this is a typo that should be corrected.
[Section 3.1, Lemma 3.5] Lemma 3.5 calls Predict deterministic, but Algorithm 3.7 samples random bits r_1,...,r_n and the success probability is over the predictor's randomness as well as the instance. The lemma should state that both algorithms are randomized, or that the guarantee holds for a fixed and publicly known seed.
[Section 3.2, proof of Lemma 3.6] The display bounding d_TV(Bias(ε̂/2t), Bias(ε/2t)) says the value is (1/2)|ε̂-ε|; the correct value, after the factor t, is |ε̂-ε|/4. The final inequality d_TV ≤ (3/4)|ε̂-ε| is unaffected, only looser than necessary.
[Theorem 3.1] The statement writes XOR(H,0) in the refutation hypothesis and XOR(H,1^n,0) elsewhere; please make the notation uniform. Also, the success probability 1 - m|ε̂-ε| - 1/poly(n) should be accompanied by a standing assumption such as m|ε̂-ε| = o(1), since the displayed quantity can be negative otherwise.
[Corollary 3.4 and Theorem 4.1 proofs] When a guessed linear system is inconsistent, the text says to "solve the linear system" without describing what to do; the algorithm should discard inconsistent runs and take the maximum only over consistent ones. In addition, the loop over "3^{2^k} functions f" should be over 3^{2^k-1} functions on the nonempty subsets of [k].

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

The paper

The paper claims

Semirandom planted recovery follows from Sum-of-Squares refutation certificates for k-XOR, at the same runtime and constraint counts that refutation already achieved.

The reading

This paper claims that solving semirandom planted CSPs — instances built on an arbitrary worst-case hypergraph but with a hidden planted structure — is no harder than refuting them. Precisely, if Sum-of-Squares can certify that a random-sign instance on the same hypergraph has value at most $1/2 + o(1)$, then an $n^{O(\ell)}$-time algorithm can identify which constraints of the planted noisy instance are corrupted and recover an assignment that is near-optimal. The proof is a generic reduction from search to refutation, which the authors say is the first for (semi)random CSPs, and instantiating it with known Sum-of-Squares refutation algorithms matches the existing refutation trade-off up to polylog factors: with $m \gtrsim (n/\ell)^{k/2}\,\ell\,\mathrm{polylog}(n)$ constraints the algorithm runs in $n^{O(\ell)}$ time and outputs an assignment whose value is within $\gamma$ of optimal. The method matters as much as the result: instead of carving the hypergraph into explicitly pseudorandom pieces, the algorithm learns which hyperedges are untrustworthy directly from the pseudo-expectation computed by the Sum-of-Squares relaxation.

What carries the argument

The load-bearing mechanism is a per-constraint noise predictor built from the Sum-of-Squares relaxation. The algorithm hides the plant by multiplying each right-hand side $b_C$ by independent random bits $r_i$, solves the degree-$2\ell$ Sum-of-Squares program that maximizes the XOR polynomial's pseudo-expectation, and outputs $\mathrm{pred}(C) = (\prod_{i\in C} r_i)\,\mathrm{sgn}(\tilde{E}[x_C])$ as its guess for whether constraint $C$ is noisy. The refutation certificate enters through the inequality that the expected number of predictor mistakes is at most $3\gamma m/13$; that bound lets a pruning stage identify a set $\mathcal{H}'$ of at least $(1-\gamma)m$ hyperedges on which the predictor is reliable, and a sample-splitting lemma turns the single input instance into $t = 20\log(mn)$ independent copies with bias $\varepsilon/2t$, so a majority vote makes every kept prediction correct simultaneously with high probability. The argument is carried by the tight coupling between the refutation slack and the predictor's mistake count: the certificate bound $1/2 + \gamma\hat{\varepsilon}/(720\log(mn))$ is exactly what forces the error small enough for Chernoff and union bounds to succeed.

Extended reading notes

Core claim

The paper's central claim is Theorem 3.1: given a semirandom planted noisy $k$-XOR instance $\Psi \sim \mathrm{XOR}(\mathcal{H}, x^*, \varepsilon)$ on an arbitrary hypergraph $\mathcal{H}$ and a bias guess $\hat{\varepsilon}$, an algorithm running in $(n+m)^{O(\ell)}$ time outputs a partition $\mathcal{H}_+ \sqcup \mathcal{H}_- \sqcup \mathcal{H}_0$ of the constraints such that every constraint it keeps is correctly de-noised — $b_C = x^*_C$ on $\mathcal{H}_+$ and $b_C = -x^*_C$ on $\mathcal{H}_-$ — and at most $\gamma|\mathcal{H}|$ constraints are discarded, provided degree-$\ell$ Sum-of-Squares certifies that a random-sign instance on the same $\mathcal{H}$ has value at most $1/2 + \gamma\hat{\varepsilon}/(720\log(mn))$. With the known Sum-of-Squares refutation algorithm for semirandom $k$-XOR supplying that certificate, the threshold becomes $m \ge c_k n (n/\ell)^{k/2-1} \log^5(n)\,\gamma^{-4}\varepsilon^{-4}$, and Gaussian elimination on the de-noised system yields an assignment with $\Psi(x) \ge \mathrm{val}(\Psi) - \gamma - o(1)$. The authors extend the same reduction to arbitrary semirandom planted Boolean $k$-CSPs, where the same constraint counts give an assignment satisfying $1-\delta$ of the constraints. The structural corollary they stress is that any future Sum-of-Squares refutation algorithm for semirandom $k$-XOR automatically yields a planted-recovery algorithm at the same parameters, so the search side inherits all progress on the refutation side.

Load-bearing premise

The entire guarantee rests on the hypothesis that degree-$2\ell$ Sum-of-Squares actually certifies the value bound $1/2 + \gamma\hat{\varepsilon}/(720\log(mn))$ for the specific adversarial hypergraph $\mathcal{H}$ when the constraint signs are random; if that certificate does not exist — which hard worst-case hypergraphs force unless P = NP — the algorithm guarantees nothing.

Editorial extensions

If this is right

Any Sum-of-Squares refutation algorithm for semirandom $k$-XOR, current or future, automatically yields a planted-recovery algorithm at the same runtime and constraint count, with a high-probability certificate as the only required ingredient.
Semirandom planted recovery now matches the refutation trade-off — $n^{O(\ell)}$ time with $m \gtrsim (n/\ell)^{k/2}\,\ell\,\mathrm{polylog}(n)$ constraints — closing the gap left by prior algorithms that reached only the dense $m \gtrsim n^{k/2}$ regime.
Because the algorithm de-noises almost every constraint simultaneously, Gaussian elimination on the cleaned system recovers an assignment whose value is at least $\mathrm{val}(\Psi) - \gamma - o(1)$, so solving the planted instance is as good as approximating the underlying worst-case instance.
The same reduction transfers to every semirandom planted Boolean $k$-CSP through the Fourier decomposition of the predicate's planting distribution, with only the $k$-XOR projections of the constraints needing refutation certificates.
The required bias guess is not an obstacle: sweeping a fine grid of $\hat{\varepsilon}$ values costs only a poly$(m)$ factor and removes the need to know the noise level.

Reading between the lines

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

The proof actually isolates one property from SoS — a bound on the predictor's expected mistake count derivable from the refutation slack — so in principle any certificate family (spectral, algebraic, or a weaker hierarchy) with the same property would plug into the reduction unchanged; this generalization is not claimed by the paper.
Although the reduction runs only in the search-from-refutation direction, it reframes the complexity comparison: a lower bound against planted recovery at a given degree would now imply a lower bound against semirandom refutation at the same degree, transferring hardness from search to refutation.
The sample-splitting lemma is a Bernoulli-factory-type operation that may be reusable elsewhere: any algorithm assuming multiple independent draws from $\mathrm{XOR}(\mathcal{H}, x^*, \varepsilon)$ can be run from a single draw by paying a bias reduction to $\varepsilon/2t$ and $2^{O(t)}$ time (or poly$(t)$ with known cloning theorems), so single-sample-to-multi-sample conversions for planted dist
A natural stress test sits at the trade-off boundary: near $m \sim (n/\ell)^{k/2}\,\ell$ the certificate should barely exist, so measuring where the de-noising pipeline's failure rate departs from its guarantee would empirically map the boundary of the search/refutation equivalence — an experiment the paper does not run.

Original abstract

We give a $n^{O(\ell)}$-time algorithm for solving semirandom planted instances of a $k$-ary Boolean constraint satisfaction problem (CSP) with $m \gtrsim \left(\frac{n}{\ell}\right)^{k/2} \ell \, \mathrm{polylog}(n)$ constraints, for any choice of the runtime parameter $\ell$. Up to $\mathrm{polylog}(n)$ factors, this matches the known runtime vs.\ number of constraints trade-off for refuting semirandom CSPs, as well as the trade-off for solving fully random planted CSPs. Prior work on designing algorithms for semirandom CSPs follows a high-level blueprint of decomposing the constraint hypergraph $\mathcal{H}$ of the instance into pieces, each with an explicit pseudorandom property that allows the standard algorithm for random CSPs to succeed on every piece. We depart considerably from this framework and instead implicitly \emph{learn} such a decomposition, without appealing directly to explicit properties such as expansion. More generally, we construct such a learning algorithm from the assumption that semirandom $k$-XOR has Sum-of-Squares certificates of refutation. This yields the broader implication that any Sum-of-Squares refutation algorithm for semirandom $k$-XOR gives a corresponding algorithm for solving semirandom planted CSPs, and instantiating this reduction with known Sum-of-Squares algorithms for refuting semirandom $k$-XOR gives our main algorithm. To the best of our knowledge, this is the first reduction from search to refutation for (semi)random CSPs.

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-11-06: 1 request, 6,010 input tokens.

What the abstract itself states, as probabilities: claims first 0.92 · states limitation 0.36 · human participants 0.01 · controlled comparison 0.05 · randomized assignment 0.12 · states quantitative result 0.97 · compares with prior results 0.96 · 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 give a $n^{O(\ell)}$-time algorithm for solving semirandom planted instances of a $k$-ary Boolean constraint satisfaction problem (CSP) with $m \gtrsim \left(\frac{n}{\ell}\right)^{k/2} \ell \, \mathrm{polylog}(n)$ constraints, for any choice of the runtime parameter $\ell$. Up to $\mathrm{polylog}(n)$ factors, this matches the known runtime vs.\ number of constraints trade-off for refuting semirandom CSPs, as well as the trade-off for solving fully random planted CSPs. Prior work on designing algorithms for semirandom CSPs follows a high-level blueprint of decomposing the constraint hypergraph $\mathcal{H}$ of the instance into pieces, each with an explicit pseudorandom property that allows the standard algorithm for random CSPs to succeed on every piece. We depart considerably from this framework and instead implicitly \emph{learn} such a decomposition, without appealing directly to explicit properties such as expansion. More generally, we construct such a learning algorithm from the assumption that semirandom $k$-XOR has Sum-of-Squares certificates of refutation. This yields the broader implication that any Sum-of-Squares refutation algorithm for semirandom $k$-XOR gives a corresponding algorithm for solving semirandom planted CSPs, and instantiating this reduction with known Sum-of-Squares algorithms for refuting semirandom $k$-XOR gives our main algorithm. To the best of our knowledge, this is the first reduction from search to refutation for (semi)random CSPs.

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 give a $n^{O(\ell)}$-time algorithm for solving semirandom planted instances of a $k$-ary Boolean constraint satisfaction problem (CSP) with $m \gtrsim \left(\frac{n}{\ell}\right)^{k/2} \ell \, \mathrm{polylog}(n)$ constraints, for any choice of the runtime parameter $\ell$.	contribution 0.61	0.96	0.70	asserted 1.00
s1	Up to $\mathrm{polylog}(n)$ factors, this matches the known runtime vs.\ number of constraints trade-off for refuting semirandom CSPs, as well as the trade-off for solving fully random planted CSPs.	interpretation 0.63	0.68	0.12	asserted 0.98
s2	Prior work on designing algorithms for semirandom CSPs follows a high-level blueprint of decomposing the constraint hypergraph $\mathcal{H}$ of the instance into pieces, each with an explicit pseudorandom property that allows the standard algorithm for random CSPs to succeed on every piece.	background 1.00	0.03	0.03	asserted 1.00
s3	We depart considerably from this framework and instead implicitly \emph{learn} such a decomposition, without appealing directly to explicit properties such as expansion.	contribution 0.52	0.94	0.06	asserted 1.00
s4	More generally, we construct such a learning algorithm from the assumption that semirandom $k$-XOR has Sum-of-Squares certificates of refutation.	method 0.65	0.90	0.13	asserted 0.99
s5	This yields the broader implication that any Sum-of-Squares refutation algorithm for semirandom $k$-XOR gives a corresponding algorithm for solving semirandom planted CSPs, and instantiating this reduction with known Sum-of-Squares algorithms for refuting semirandom $k$-XOR gives our main algorithm.	interpretation 0.85	0.91	0.59	asserted 1.00
s6	To the best of our knowledge, this is the first reduction from search to refutation for (semi)random CSPs.	contribution 0.43	0.81	0.22	asserted 0.88

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

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]

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (JACM) , 45(3):501--555, 1998

View on Pith 1998
[5]

Prashanti Anderson, Peter Manohar, and Jeff Xu. Certifiable near-optimality: A simple framework for unifying search and refutation for (semi)random csps. CoRR , abs/2609.38367, 2026

View on Pith Pith review arXiv 2026
[6]

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
[7]

Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of np. Journal of the ACM (JACM) , 45(1):70--122, 1998

View on Pith 1998
[8]

Matthew Brennan and Guy Bresler. Reducibility and statistical-computational gaps from secret leakage. In Proceedings of Thirty Third Conference on Learning Theory , volume 125 of Proceedings of Machine Learning Research , pages 648--847. PMLR, 09--12 Jul 2020

View on Pith 2020
[9]

Matthew Brennan, Guy Bresler, and Wasim Huleihel. Universality of computational lower bounds for submatrix detection. In Proceedings of the Thirty-Second Conference on Learning Theory , volume 99 of Proceedings of Machine Learning Research , pages 417--468. PMLR, 25--28 Jun 2019

View on Pith 2019
[10]

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
[11]

Arpon Basu, Jun - Ting Hsieh, Andrew D. Lin, and Peter Manohar. Solving random planted csps below the n$ ^ k/2 $ threshold. In 53rd International Colloquium on Automata, Languages, and Programming, ICALP 2026, Royal Holloway, University of London, Egham, United Kingdom, July 7-10, 2026 , volume 374 of LIPIcs , pages 23:1--23:22. Schloss Dagstuhl - Leibn...

View on Pith Pith review arXiv 2026
[12]

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
[13]

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
[14]

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

View on Pith 2016
[15]

Andrei A. Bulatov. A dichotomy theorem for nonuniform csps. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 319--330, 2017

View on Pith 2017
[16]

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
[17]

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
[18]

Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing , STOC '71, page 151–158, New York, NY, USA, 1971. Association for Computing Machinery

View on Pith 1971
[19]

Siu On Chan, Tommaso d' Orsi, and Jeff Xu. Strongly refuting random CSP without literals. CoRR , abs/2604.27336, 2026

View on Pith Pith review arXiv 2026
[20]

Irit Dinur. The pcp theorem by gap amplification. J. ACM , 54(3):12–es, 2007

View on Pith 2007
[21]

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
[22]

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
[23]

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
[24]

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
[25]

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
[26]

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
[27]

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

View on Pith 2000
[28]

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

View on Pith 2001
[29]

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
[30]

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
[31]

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
[32]

Pravesh K. Kothari. Kikuchi graphs of random hypergraphs are approximately johnson. CoRR , abs/2606.08597, 2026

View on Pith Pith review arXiv 2026
[33]

Leonid A. Levin. Universal sequential search problems. Problems of Information Transmission , 9(3):265--266, 1973

View on Pith 1973
[34]

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
[35]

Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing , STOC '78, page 216–226, New York, NY, USA, 1978. Association for Computing Machinery

View on Pith 1978
[36]

Dmitriy Zhuk. A proof of the csp dichotomy conjecture. J. ACM , 67(5), August 2020

View on Pith 2020

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]

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (JACM) , 45(3):501--555, 1998

View on Pith 1998

[5] [5]

Prashanti Anderson, Peter Manohar, and Jeff Xu. Certifiable near-optimality: A simple framework for unifying search and refutation for (semi)random csps. CoRR , abs/2609.38367, 2026

View on Pith Pith review arXiv 2026

[6] [6]

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

[7] [7]

Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of np. Journal of the ACM (JACM) , 45(1):70--122, 1998

View on Pith 1998

[8] [8]

Matthew Brennan and Guy Bresler. Reducibility and statistical-computational gaps from secret leakage. In Proceedings of Thirty Third Conference on Learning Theory , volume 125 of Proceedings of Machine Learning Research , pages 648--847. PMLR, 09--12 Jul 2020

View on Pith 2020

[9] [9]

Matthew Brennan, Guy Bresler, and Wasim Huleihel. Universality of computational lower bounds for submatrix detection. In Proceedings of the Thirty-Second Conference on Learning Theory , volume 99 of Proceedings of Machine Learning Research , pages 417--468. PMLR, 25--28 Jun 2019

View on Pith 2019

[10] [10]

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

[11] [11]

Arpon Basu, Jun - Ting Hsieh, Andrew D. Lin, and Peter Manohar. Solving random planted csps below the n\( ^ k/2 \) threshold. In 53rd International Colloquium on Automata, Languages, and Programming, ICALP 2026, Royal Holloway, University of London, Egham, United Kingdom, July 7-10, 2026 , volume 374 of LIPIcs , pages 23:1--23:22. Schloss Dagstuhl - Leibn...

View on Pith Pith review arXiv 2026

[12] [12]

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

[13] [13]

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

[14] [14]

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

View on Pith 2016

[15] [15]

Andrei A. Bulatov. A dichotomy theorem for nonuniform csps. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 319--330, 2017

View on Pith 2017

[16] [16]

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

[17] [17]

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

[18] [18]

Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing , STOC '71, page 151–158, New York, NY, USA, 1971. Association for Computing Machinery

View on Pith 1971

[19] [19]

Siu On Chan, Tommaso d' Orsi, and Jeff Xu. Strongly refuting random CSP without literals. CoRR , abs/2604.27336, 2026

View on Pith Pith review arXiv 2026

[20] [20]

Irit Dinur. The pcp theorem by gap amplification. J. ACM , 54(3):12–es, 2007

View on Pith 2007

[21] [21]

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

[22] [22]

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

[23] [23]

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

[24] [24]

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

[25] [25]

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

[26] [26]

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

[27] [27]

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

View on Pith 2000

[28] [28]

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

View on Pith 2001

[29] [29]

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

[30] [30]

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

[31] [31]

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

[32] [32]

Pravesh K. Kothari. Kikuchi graphs of random hypergraphs are approximately johnson. CoRR , abs/2606.08597, 2026

View on Pith Pith review arXiv 2026

[33] [33]

Leonid A. Levin. Universal sequential search problems. Problems of Information Transmission , 9(3):265--266, 1973

View on Pith 1973

[34] [34]

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

[35] [35]

Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing , STOC '78, page 216–226, New York, NY, USA, 1978. Association for Computing Machinery

View on Pith 1978

[36] [36]

Dmitriy Zhuk. A proof of the csp dichotomy conjecture. J. ACM , 67(5), August 2020

View on Pith 2020