The "cut-matching game" is a particular zero-sum game between two players where the objective of the players is to minimize (maximize) the number of rounds before the graph has large expansion. This game, which is interesting in itself, lies at the heart of very fast algorithms for graph partitioning with provable approximation guarantees. The running time of these algorithms is dominated by poly-logn invocations of single commodity max-flow. The approximation factor achieved by the algorithms turns out to be the number of rounds of the cut-matching game. The best upper bound is currently O(log n) and there is a lower bound of \Omega(\sqrt{log n}). The lower bound matches the approximation factor achieved by algorithm of ARV, and one might speculate that this is no coincidence, but that the cut-matching game provides a good structured setting in which to study the complexity of sparsest cuts. In this talk I will survey these and related results.

Biography：

Umesh Virkumar Vazirani is a Professor of Computer Science at the University of California, Berkeley. His research interests lie primarily in quantum computing. He is also the author of a textbook on algorithms. He is the brother of Georgia Tech College of Computing professor Vijay Vazirani. In 2005 they both were inducted as Fellows of the Association for Computing Machinery.

He received an NSF Presidential Young Investigator Award in 1987 and the Friedman Mathematics Prize in 1985. He is currently at the forefront of research in the area of quantum computing.

Umesh Vazirani received his B.Tech in computer science from M.I.T. in 1981 and his PhD in computer science from U.C. Berkeley in 1985. He is currently professor of computer science at U.C. Berkeley and director of BQIC - the Berkeley Center for Quantum Information and Computation. Prof. Vazirani is a theoretician with broad interests in novel models of computation.He has done seminal work in quantum computation and on the computational foundations of randomness. His books include “An Introduction to Computational Learning Theory” (with Michael Kearns, MIT Press, 1995), and “Algorithms” (with Sanjoy Dasgupta and Christos Papadimitriou, MIT press, 2006).