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

CREATORJoshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE226 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-13345

Browse the full library · About the Tower of Babel