Optimal Spectral Gaps | Richard M. Karp Distinguished Lecture
Oct 14, 2026
Ramon van Handel
A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length
Computer Science and Mathematics seminar by Vijay V. Vazirani, University of California, Irvine
Hosted by Simons Institute for the Theory of Computing, UC Berkeley
Wednesday 14:00 Los Angeles (GMT-7)
Recording available
Berkeley, United States
Abstract
Vijay V. Vazirani presents a two-part account of the Micali–Vazirani algorithm for maximum-cardinality matching. The first part develops background from bipartite matching and Edmonds’ algorithm, explains why shortest augmenting paths create difficulties, and introduces double depth-first search. The second develops a structural theory of alternating paths and blossoms that supports the algorithm and its recently completed proof.
Topics
Micali–Vazirani algorithmmaximum-cardinality matchingbipartite matchingEdmonds’ algorithmshortest augmenting pathsdouble depth-first searchalternating pathsblossoms
Show 1 more topic
augmenting paths
More from Simons Institute for the Theory of Computing, UC Berkeley
All talksMy Favorite Expanders | Richard M. Karp Distinguished Lecture
Sep 29, 2026Ryan O'DonnellEncrypting to a Mathematical Fact | Theoretically Speaking
Video · 1 h 24 min · Captions · Jul 15, 2026Sanjam GargResponsibly Improving AI with Privacy-Sensitive Data: Principles, Theory, and Practice | Richard M. Karp Distinguished Lecture
Video · 1 h 10 min · Captions · Feb 24, 2026Brendan McMahan