{"ID":2881298,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.13345","arxiv_id":"2508.13345","title":"Tight Bounds for Sparsifying Random CSPs","abstract":"The problem of CSP sparsification asks: for a given CSP instance, what is the sparsest possible reweighting such that for every possible assignment to the instance, the number of satisfied constraints is preserved up to a factor of $1 \\pm ε$? We initiate the study of the sparsification of random CSPs. In particular, we consider two natural random models: the $r$-partite model and the uniform model. In the $r$-partite model, CSPs are formed by partitioning the variables into $r$ parts, with constraints selected by randomly picking one vertex out of each part. In the uniform model, $r$ distinct vertices are chosen at random from the pool of variables to form each constraint. In the $r$-partite model, we exhibit a sharp threshold phenomenon. For every predicate $P$, there is an integer $k$ such that a random instance on $n$ vertices and $m$ edges cannot (essentially) be sparsified if $m \\le n^k$ and can be sparsified to size $\\approx n^k$ if $m \\ge n^k$. Here, $k$ corresponds to the largest copy of the AND which can be found within $P$. Furthermore, these sparsifiers are simple, as they can be constructed by i.i.d. sampling of the edges. In the uniform model, the situation is a bit more complex. For every predicate $P$, there is an integer $k$ such that a random instance on $n$ vertices and $m$ edges cannot (essentially) be sparsified if $m \\le n^k$ and can sparsified to size $\\approx n^k$ if $m \\ge n^{k+1}$. However, for some predicates $P$, if $m \\in [n^k, n^{k+1}]$, there may or may not be a nontrivial sparsifier. In fact, we show that there are predicates where the sparsifiability of random instances is non-monotone, i.e., as we add more random constraints, the instances become more sparsifiable. We give a precise (efficiently computable) procedure for determining which situation a specific predicate $P$ falls into.","short_abstract":"The problem of CSP sparsification asks: for a given CSP instance, what is the sparsest possible reweighting such that for every possible assignment to the instance, the number of satisfied constraints is preserved up to a factor of $1 \\pm ε$? We initiate the study of the sparsification of random CSPs. In particular, we...","url_abs":"https://arxiv.org/abs/2508.13345","url_pdf":"https://arxiv.org/pdf/2508.13345v2","authors":"[\"Joshua Brakensiek\",\"Venkatesan Guruswami\",\"Aaron Putterman\"]","published":"2025-08-18T20:04:07Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\",\"math.CO\"]","methods":"[]","has_code":false}