Truly linear sparsifier conjecture for set systems
Truly linear sparsifier conjecture for set systems
Let be a set system, let be weights, and let . Write for the chain length of . A sparsifier retains a selected subset of coordinates while approximating the relevant set-system quantities within multiplicative error . Truly linear sparsifier conjecture. There exists a sparsifier of retaining only
many coordinates. This conjecture seeks an analogue for arbitrary set systems of the edge bounds for graph cut sparsification; the paper's results give sparsifiers whose size depends on accuracy and chain length, but do not establish this bound in general.
Sources & referencesView supporting material
Primary source
Joshua Brakensiek, Venkatesan Guruswami and Aaron Putterman, “Multiplicative error set system sparsification: A simpler proof via chain length contraction”, arXiv:2605.01508 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.