What was already known
Chen, Khanna and Li used bits for weighted turnstile cut sparsification, with polynomial recovery time.
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.
- Acknowledgements on Gemini and the authors’ proof checkAI work and human attribution
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
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 and , the algorithm uses bits, polylogarithmic worst-case update time and worst-case recovery time. With probability at least , the output preserves every cut within a factor of .
- 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 and , the algorithm uses bits, polylogarithmic worst-case update time and worst-case recovery time. With probability at least , the output preserves every cut within a factor of .
- Basis
- Reported by the linked checker
- Theorem 1.1 and the scope of its Lean checkTheorem 1.1 and the scope of its Lean check
- Lean files for cut sparsificationLean files for cut sparsification
Human understanding
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
Linked directly to the manuscript’s acknowledgements.
Read this published revisionAdded a reviewed earlier manuscript to the research catalog.
Read this published revision