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.

You are reading an earlier published revision. Read the current record.

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.

This revision has no four-dimension assessment. Read the criteria.

AI involvement

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

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

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

Other useful sources

Correction and publication history