All-Pairs Min-Cut vs. All-Pairs Shortest-Path - Amir Abboud
From Institute for Advanced Study
Computer Science/Discrete Mathematics Seminar I 10:30am|Simonyi 101 and Remote Access Topic: All-Pairs Min-Cut vs. All-Pairs Shortest-Path Speaker: Amir Abboud Affiliation: Weizmann Institute of Science Date: January 20, 2026 The All-Pairs Min-Cut problem (APMC) asks to compute the minimum cut (or equivalently, the maximum flow) between all pairs of nodes in a graph.1 The naive solution of making n^2 calls to a single-pair min-cut algorithm was surpassed in 1961 by a remarkable algorithm of G...
Mentioned in This Episode
- Graph (concept)
- Gomory (person)
- Max Flow (concept)
- Shortest Path (concept)
- All Pairs Shortest Path (concept)
- Dijkstra (person)
- Matrix Multiplication (concept)
- Expander Decomposition (concept)
- The BSG Theorem (concept)
- Jason Lee (person)
- Additive Combinatorics (concept)
- Boolean Matrix Multiplication (concept)
- Steiner Tree Packing (concept)
- Triangle Detection (concept)
- K Click (concept)
- Polynomial Frame Ruia Conjecture (concept)
- Ted Talks (event)
- Olympics (event)
- World Cup (event)
- The Burning Man (event)