# How to refute a random CSP

arXiv: https://arxiv.org/abs/1505.04383 · HTML: https://mlsanity.com/paper/1505.04383/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 May 2015.

## Built on by (most cited first, 3 of 3)

- [The Probably Approximately Correct Learning Model in Computational Learning Theory](https://mlsanity.com/paper/2511.08791/) (2025)
- [A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs](https://mlsanity.com/paper/2204.10881/) (2022)
- [Overcomplete Tensor Decomposition via Koszul-Young Flattenings](https://mlsanity.com/paper/2411.14344/) (2024)

## Abstract (arXiv)

Let P be a k-ary predicate over a finite alphabet. Consider a random CSP(P) instance I over n variables with m constraints. When m gg n the instance I will be unsatisfiable with high probability, and we want to find a refutation - i.e., a certificate of unsatisfiability. When P is the 3-ary OR predicate, this is the well studied problem of refuting random 3-SAT formulas, and an efficient algorithm is known only when m gg n3/2. Understanding the density required for refutation of other predicates is important in cryptography, proof complexity, and learning theory. Previously, it was known that for a k-ary predicate, having m gg nlceil k/2 rceil constraints suffices for refutation. We give a criterion for predicates that often yields efficient refutation algorithms at much lower densities. Specifically, if P fails to support a t-wise uniform distribution, then there is an efficient algorithm that refutes random CSP(P) instances I whp when m gg nt/2. Indeed, our algorithm will "somewhat strongly" refute I, certifying Opt(I) ≤ 1-Omegak(1), if t = k then we get the strongest possible refutation, certifying Opt(I) ≤ E[P] + o(1). This last result is new even in the context of random k-SAT. Regarding the optimality of our m gg nt/2 requirement, prior work on SDP hierarchies has given some evidence that efficient refutation of random CSP(P) may be impossible when m ll nt/2. Thus there is an indication our algorithm's dependence on m is optimal for every P, at least in the context of SDP hierarchies. Along these lines, we show that our refutation algorithm can be carried out by the O(1)-round SOS SDP hierarchy. Finally, as an application of our result, we falsify assumptions used to show hardness-of-learning results in recent work of Daniely, Linial, and Shalev-Shwartz.