Title: The CutMatching Game and Fast Algorithms for Graph Partitioning  
Name: Umesh Vazirani University of California, Berkeley 

Time:October 15th (Wednesday) 10:3011:15  
Location: Lecture Hall, FIT Building, Tsinghua University  
Host Unit: ITCS, Tsinghua University 
The "cutmatching game" is a particular zerosum 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 polylogn invocations of single commodity maxflow. The approximation factor achieved by the algorithms turns out to be the number of rounds of the cutmatching 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 cutmatching 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.
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).