2026-09-08T02:22:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26433 2026-09-05T19:43:20Z ddc:004 open_access

Multiplicative Error Set System Sparsification: A Simpler Proof via Chain Length Contraction Brakensiek, Joshua Guruswami, Venkatesan Putterman, Aaron constraint satisfaction problem chain length sparsification VC dimension The chain length of a set family 𝒮 ⊆ 2^[m] is the largest ascending sequence of sets in containment order in the union-closure of S. In this work, we provide a significantly simpler and more optimal characterization of the sparsifiability of set systems in terms of their chain length, improving on the work of Brakensiek and Guruswami [STOC 2025]. Our proof relies on a generalization of Karger’s [SODA 1993] famous contraction algorithm and its recent linear algebraic extensions [Khanna-Putterman-Sudan SODA 2024], and our resulting bounds show that, just as VC dimension characterizes the additive sparsifiability of a set system, chain length governs the multiplicative sparsifiability. As a corollary, we obtain improved bounds for weighted CSP sparsification. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joshua Brakensiek and Venkatesan Guruswami and Aaron Putterman 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.44 urn:nbn:de:0030-drops-264331 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.44 eng https://creativecommons.org/licenses/by/4.0/legalcode