Tight Bounds for Sparsifying Random CSPs
Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman · 2025
Read Tight Bounds for Sparsifying Random CSPs by Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-13345.txt.
Introduction
Joshua Brakensiek, Venkatesan Guruswami, and Aaron Putterman open the study of sparsifying random constraint satisfaction problems. Sparsification shrinks a problem instance by reweighting a few constraints while keeping every assignment's score nearly unchanged. The authors ask how small such a stand-in can be when the instance is random, under two natural random models.
In the partite model, a sharp threshold appears. Below a certain density no real sparsification exists, and above it a simple random sampling of constraints works. The threshold is set by the largest AND pattern hidden in the predicate. The uniform model behaves similarly but leaves a middle band where the answer depends on the predicate. Surprisingly, for some predicates sparsifiability is not monotone: adding constraints can first help, then hurt.
Catalog record
| CREATOR | Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 226 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-13345