# Minimum Cut in O(mlog2 n) Time

arXiv: https://arxiv.org/abs/1911.01145 · HTML: https://mlsanity.com/paper/1911.01145/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2019.

## Built on by (most cited first, 4 of 4)

- [On the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2202.13736/) (2022)
- [Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2207.00956/) (2022)
- [Extensions of Karger's Algorithm: Why They Fail in Theory and How They Are Useful in Practice](https://mlsanity.com/paper/2110.02750/) (2021)
- [The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for ℓ2 Norm Estimation](https://mlsanity.com/paper/2507.16345/) (2025)

## Abstract (arXiv)

We give a randomized algorithm that finds a minimum cut in an undirected weighted m-edge n-vertex graph G with high probability in O(m log2 n) time. This is the first improvement to Karger's celebrated O(m log3 n) time algorithm from 1996. Our main technical contribution is a deterministic O(m log n) time algorithm that, given a spanning tree T of G, finds a minimum cut of G that 2-respects (cuts two edges of) T.