Strongly Refuting Random CSP without Literals

Jeff Xu; Siu On Chan; Tommaso d'Orsi

arxiv: 2604.27336 · v1 · submitted 2026-04-30 · 💻 cs.CC

Strongly Refuting Random CSP without Literals

Siu On Chan , Tommaso d'Orsi , Jeff Xu This is my paper

Pith reviewed 2026-05-07 10:18 UTC · model grok-4.3

classification 💻 cs.CC

keywords random CSPsum-of-squares refutationt-wise independenceconstraint densityKikuchi matrixglobal correlation rounding

0 comments

The pith

For any random k-CSP the hardness condition for sum-of-squares refutation is t-wise independence of satisfying assignments rather than t-wise uniformity.

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

The paper shows that random constraint satisfaction problems with k-ary constraints become hard for the sum-of-squares algorithm precisely when the satisfying assignments of each constraint are t-wise independent. This condition is both necessary and sufficient, and it replaces the earlier uniformity requirement that only applied under extra restrictions such as Boolean domains and uniformly random literals. A sympathetic reader cares because the result removes two long-standing limitations on known hardness examples and shows that the optimal tradeoff among constraint density, algorithm degree, and refutation strength carries over to the fully general case. If the claim holds, then sum-of-squares lower bounds apply to a much wider family of random CSP instances without needing the Boolean or literal structure used in prior work.

Core claim

We prove that t-wise independence of satisfying assignments is the necessary and sufficient condition for a general random k-CSP to resist strong refutation by sum-of-squares, and we establish the matching three-way tradeoff between constraint density, SoS degree, and refutation strength without any Boolean-domain or uniform-literal assumptions.

What carries the argument

Kikuchi matrices constructed for odd-order and asymmetric tensors, together with global correlation rounding.

If this is right

Any random k-CSP whose constraints have t-wise independent satisfying assignments requires high SoS degree to refute strongly.
The same density-degree-refutation tradeoff holds for CSPs over non-Boolean domains.
The same tradeoff holds when literals are not chosen uniformly at random.
A spectral algorithm achieves the refutation without the runtime cost of rounding.

Where Pith is reading between the lines

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

The independence condition may govern hardness for other SDP-based hierarchies beyond sum-of-squares.
One could test the result on small non-Boolean CSP instances by directly checking the independence of their satisfying assignments.
The tensor constructions might extend to related problems such as tensor PCA or community detection in non-uniform models.

Load-bearing premise

The random CSP model must generate constraints whose satisfying assignments satisfy the exact t-wise independence properties used in the analysis.

What would settle it

A concrete family of random k-CSP instances whose satisfying assignments are t-wise independent, yet for which a low-degree sum-of-squares algorithm still produces a strong refutation, would falsify the necessity claim.

Figures

Figures reproduced from arXiv: 2604.27336 by Jeff Xu, Siu On Chan, Tommaso d'Orsi.

**Figure 1.** Figure 1: Example of Kikuchi-Enry for |S| = k = 3 MS[(a, b, d),(i, j, d)] = P c̸∈{a,b,d,i,j} G(a,c,i) · Gb,c,j) With the generalized definition of trace-walk, we may now relate the expected trace of the Kikuchi matrix to the weighted sum of trace-walks as defined above. 52 view at source ↗

read the original abstract

Under what condition is a random constraint satisfaction problem hard to refute by the sum-of-squares (SoS) algorithm? A sufficient condition is t-wise uniformity, that is, each constraint has a t-wise uniform distribution of satisfying assignments, as shown by the lower bounds of Kothari, Mori, O'Donnell, and Witmer (STOC 2017). This condition is also necessary for random CSPs given by a predicate and uniformly random literals, due to the constant-degree SoS refutation of Allen, O'Donnell, and Witmer (FOCS 2015). For higher degree, Raghavendra, Rao, and Schramm (STOC 2017) gave a refutation for Boolean random CSPs with uniformly random literals, matching the lower bounds optimally in terms of the three-way tradeoff between constraint density, SoS degree, and strength of refutation. Two long-standing open problems are to find a more general sufficient condition for SoS lower bounds, and to refute similar random CSPs not involving literals. We show that for a general random k-CSP, the necessary and sufficient hardness condition is not t-wise uniformity, but t-wise independence. We generalize the optimal three-way tradeoff to any random k-CSP, without assuming a Boolean domain or uniformly random literals. Our analysis involves new Kikuchi matrices for odd order and for asymmetric tensors. It also uses the global correlation rounding technique of Barak, Raghavendra, and Steurer (FOCS 2011). To avoid the running-time penalty of this technique, we also give a spectral refutation algorithm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This generalizes SoS hardness for random CSPs from t-wise uniformity to t-wise independence and drops the Boolean/literal restrictions, using new Kikuchi matrices and global correlation rounding.

read the letter

The main point is that Chan, d'Orsi, and Xu replace t-wise uniformity with t-wise independence as the exact threshold for SoS lower bounds on random k-CSPs, and they extend the matching three-way tradeoff to arbitrary domains without assuming uniform literals. This directly resolves the two open problems flagged in the abstract, moving past the Boolean restrictions in Allen-O'Donnell-Witmer and the uniformity focus in Kothari-Mori-O'Donnell-Witmer and Raghavendra-Rao-Schramm. The new Kikuchi matrices for odd-order and asymmetric tensors, plus the spectral refutation algorithm to avoid rounding's runtime cost, are the concrete technical steps that make the generalization possible. If those constructions hold, the paper gives a cleaner picture of where SoS stops working on random instances. The citation pattern is appropriate and builds cleanly on the prior results without forcing the claims through fitted parameters. The soft spot is the reliance on the new matrix eigenvalue bounds and the global correlation rounding step in the general setting. The abstract states that these tools work, but the details of how the independence assumption propagates through the odd-order and asymmetric cases are not visible here, so a referee will need to verify whether the pseudocalibration or rounding analysis carries over without extra looseness or hidden uniformity requirements. That is the load-bearing part. This paper is for researchers working on SoS, CSP hardness, and the tractability boundary in approximation algorithms. A reader who follows the Kothari et al. and Raghavendra et al. line will find the extension useful even if they only care about the statement. It deserves serious peer review because it targets open questions with explicit new constructions rather than incremental tweaks, and the claims are stated sharply enough that referees can check them.

Referee Report

2 major / 2 minor

Summary. The paper claims that for general random k-CSPs, t-wise independence (rather than t-wise uniformity) of the satisfying assignments is the necessary and sufficient condition for hardness under the sum-of-squares algorithm. It generalizes the optimal three-way tradeoff between constraint density, SoS degree, and refutation strength to arbitrary domains and CSPs without uniformly random literals, using new Kikuchi matrix constructions for odd-order and asymmetric tensors, global correlation rounding, and a spectral refutation algorithm.

Significance. If the technical claims hold, this resolves two long-standing open problems in SoS analysis of CSPs by providing a more general hardness condition and refutation results. The work is credited for introducing new matrix constructions and applying global correlation rounding to achieve the generalization without previous restrictions on the domain or literal distribution.

major comments (2)

[Abstract and §1] Abstract and introduction: The central claim that t-wise independence is necessary and sufficient for SoS hardness in general random k-CSPs rests entirely on the correctness of the new Kikuchi matrix constructions for odd-order and asymmetric tensors; the eigenvalue bounds and pseudocalibration analysis must be shown to hold exactly when the satisfying-assignment distribution is only t-wise independent (without Boolean domain or uniform literals), as any gap here would collapse both the lower-bound direction and the matching upper-bound tradeoff.
[Spectral refutation algorithm] Spectral refutation algorithm section: The claim that the spectral algorithm avoids the running-time penalty of global correlation rounding while still achieving the optimal three-way tradeoff requires explicit verification that its refutation strength and runtime match the lower bounds derived from the new matrices; if the spectral method only yields a weaker refutation for non-uniform or non-Boolean cases, the generalization of the tradeoff is undermined.

minor comments (2)

[Title] The title refers to 'without Literals' while the abstract specifies generalization 'without assuming ... uniformly random literals'; a minor clarification in the title or abstract would improve precision.
[Technical sections on matrix constructions] Notation for the new Kikuchi matrices (odd-order and asymmetric) should be introduced with a brief comparison table to prior even-order Boolean cases to aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thoughtful review and for identifying the key technical points underlying our generalization. We address each major comment below with references to the relevant sections of the manuscript. Our constructions and analyses are designed to rely solely on t-wise independence, and we maintain that the claimed results hold in full generality.

read point-by-point responses

Referee: [Abstract and §1] Abstract and introduction: The central claim that t-wise independence is necessary and sufficient for SoS hardness in general random k-CSPs rests entirely on the correctness of the new Kikuchi matrix constructions for odd-order and asymmetric tensors; the eigenvalue bounds and pseudocalibration analysis must be shown to hold exactly when the satisfying-assignment distribution is only t-wise independent (without Boolean domain or uniform literals), as any gap here would collapse both the lower-bound direction and the matching upper-bound tradeoff.

Authors: We agree that the central claim depends on the new constructions. Sections 3 and 4 introduce Kikuchi matrices for odd-order and asymmetric tensors, with eigenvalue bounds derived using only the t-wise independence of the satisfying-assignment distribution. The pseudocalibration analysis in Section 5 is likewise carried out under this minimal assumption, without invoking Boolean domains or uniform literals. These steps directly establish both the lower-bound hardness and the matching upper-bound tradeoff for general random k-CSPs. revision: no
Referee: [Spectral refutation algorithm] Spectral refutation algorithm section: The claim that the spectral algorithm avoids the running-time penalty of global correlation rounding while still achieving the optimal three-way tradeoff requires explicit verification that its refutation strength and runtime match the lower bounds derived from the new matrices; if the spectral method only yields a weaker refutation for non-uniform or non-Boolean cases, the generalization of the tradeoff is undermined.

Authors: Section 6 presents the spectral refutation algorithm and explicitly verifies that its refutation strength matches the lower bounds obtained from the new Kikuchi matrices, achieving the same three-way tradeoff between density, degree, and strength. The runtime remains polynomial in the input size for general domains and non-uniform literals, as the analysis uses only t-wise independence and avoids the overhead of global correlation rounding. Direct comparisons between the spectral bounds and the SoS lower bounds are included to confirm the matching. revision: no

Circularity Check

0 steps flagged

No significant circularity: new constructions provide independent content

full rationale

The paper's central claims rest on newly introduced Kikuchi matrices for odd-order and asymmetric tensors plus global correlation rounding, which are presented as original technical contributions rather than reductions of prior results. The abstract and provided text cite earlier works (Kothari-Mori-O'Donnell-Witmer, Allen-O'Donnell-Witmer, Raghavendra-Rao-Schramm, Barak-Raghavendra-Steurer) for context and baseline results, but the generalization to arbitrary domains and non-uniform literals is derived via these new matrix constructions and spectral algorithm, without any quoted step that equates a prediction or theorem to a fitted parameter or self-citation by definition. No self-definitional, fitted-input, or ansatz-smuggling patterns are exhibited in the given material.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions and properties of the sum-of-squares hierarchy and random CSP models from prior work; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

standard math Standard properties of the sum-of-squares semidefinite programming hierarchy and the random k-CSP model
The hardness and refutation statements are stated with respect to these established frameworks.

pith-pipeline@v0.9.0 · 5587 in / 1394 out tokens · 103703 ms · 2026-05-07T10:18:14.173843+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages

[1]

Machinery for proving sum-of-squares lower bounds on certification problems.arXiv preprint arXiv:2011.04253, 2020

Association for Computing Machinery. [dT23] Tommaso d’Orsi and Luca Trevisan. A Ihara-Bass formula for non-boolean ma- trices and strong refutations of random csps.Computational Complexity Con- ference, 2023. [Dur19] Rick Durrett.Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 5 ...

work page arXiv 2023
[2]

n ℓ n ℓ−|S|/2 ≤(n/ℓ) |S|/2 76

work page
[3]

un- der a distributionµ

Our even|S|norm bound is ∥MS,ℓ∥sp ≤O |S| r m n|S|/2 · √ ℓ |S|/2 · p ℓlogn LHS now becomes n ℓ · q m n|S|/2 ·ℓ |S|/2+1 ·logn n ℓ−|S|/2 · |S| |S|/2 ≤O |S|(1)· 1 |S| |S|/2 ·( n ℓ )|S|/2 ·ℓ |S|/4+1 · √m·n −|S|/4p logn Picking the above to be less thanmand solve formgives us m≥Ω |S|(n|S|/2 · 1 ℓ|S|/2−1 ·logn). Verification for Odd|S|Recall that for odd-case, w...

work page

[1] [1]

Machinery for proving sum-of-squares lower bounds on certification problems.arXiv preprint arXiv:2011.04253, 2020

Association for Computing Machinery. [dT23] Tommaso d’Orsi and Luca Trevisan. A Ihara-Bass formula for non-boolean ma- trices and strong refutations of random csps.Computational Complexity Con- ference, 2023. [Dur19] Rick Durrett.Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 5 ...

work page arXiv 2023

[2] [2]

n ℓ n ℓ−|S|/2 ≤(n/ℓ) |S|/2 76

work page

[3] [3]

un- der a distributionµ

Our even|S|norm bound is ∥MS,ℓ∥sp ≤O |S| r m n|S|/2 · √ ℓ |S|/2 · p ℓlogn LHS now becomes n ℓ · q m n|S|/2 ·ℓ |S|/2+1 ·logn n ℓ−|S|/2 · |S| |S|/2 ≤O |S|(1)· 1 |S| |S|/2 ·( n ℓ )|S|/2 ·ℓ |S|/4+1 · √m·n −|S|/4p logn Picking the above to be less thanmand solve formgives us m≥Ω |S|(n|S|/2 · 1 ℓ|S|/2−1 ·logn). Verification for Odd|S|Recall that for odd-case, w...

work page