Weighted cut sparsification in turnstile streams

A graph arrives as a stream of updates that can raise or lower edge weights. Can one pass produce a sparse reweighted subgraph that approximates the weight of every cut?

Why it matters and what counts as progress

Why it matters: A sparsifier lets graph algorithms work with a smaller input. A stream algorithm must build it while retaining much less information than the full list of updates.

What counts as progress: Compare space, time per update and recovery time for the same weighted stream model. The stated probability must cover every cut simultaneously.

How the problem developed

  1. 2022 · Weighted turnstile sketch [5]

    Yu Chen, Sanjeev Khanna and Huan Li Gave a sketch for producing a cut sparsifier under general weight updates.

  2. 2 Nov 2026 · Near-optimal space and time [1][3]

    Lin, Mirrokni and Woodruff with Gemini 4 Improved the space bound and obtained near-linear recovery at fixed accuracy.

AI contribution

Near-Optimal Space and Time Cut Sparsification in Turnstile Streams

Honghao Lin, Vahab Mirrokni, David P. Woodruff

Lin, Mirrokni and Woodruff give a one-pass linear sketch for weighted turnstile graph streams. For 0<ε<10<\varepsilon<1 and 0<δ<1/40<\delta<1/4, the algorithm uses O~(n/ε2)\widetilde O(n/\varepsilon^2) bits, polylogarithmic worst-case update time and O~(n/ε2)\widetilde O(n/\varepsilon^2) worst-case recovery time. With probability at least 1−δ1-\delta, the output preserves every cut within a factor of 1±ε1\pm\varepsilon.

AI involvementAI-led
ImportanceNotable
Technical verificationFormal (Lean + human)
Human understandingFew
Paper date:

Sources

  1. Lin, Mirrokni and Woodruff’s paper
  2. Acknowledgements on Gemini and the authors’ proof check
  3. Theorem 1.1 and the scope of its Lean check
  4. Lean files for cut sparsification
  5. Chen, Khanna and Li’s weighted graph sketches
  6. Acknowledgements on Gemini and the authors’ proof check
Publication history