Near-Optimal Space and Time Cut Sparsification in Turnstile Streams

Get email updates

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.

What was already known

Chen, Khanna and Li used O~(n/ε3)\widetilde O(n/\varepsilon^3) bits for weighted turnstile cut sparsification, with polynomial recovery time.

AI involvement AI-led

The authors first developed a solution with an issue in its proof. They credit Gemini 4 via Stellar Colosseum with a new proof of the near-optimal-space algorithm and with the subsequent running-time improvement.

Importance Notable

The result removes a factor of one over the error tolerance from the prior space bound and brings recovery time close to the size of the output.

Technical verification Formal (Lean + human)

Lin, Mirrokni and Woodruff report checking the proof. They also report that Lean verifies Theorem 1.1 with the approximate Gomory–Hu tree algorithm as a hypothesis.

Independent checking

The authors report verifying the proof of their algorithm.

Checker
Honghao Lin, Vahab Mirrokni and David P. Woodruff
Scope
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.
Basis
Reported by the linked checker

Formal checking

Checked Theorem 1.1 conditional on the approximate Gomory–Hu tree algorithm.

Checker
Lean, as reported by Lin, Mirrokni and Woodruff
Scope
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.
Basis
Reported by the linked checker

Human understanding Few

The acknowledgements identify who checked the proof. They leave the attribution of the explanation of the central sampling argument open.

Other useful sources

Correction and publication history