CATS-Apr-11-2014

Title

The Theory of Equilibrium Computation Has Come Of Age

Speaker

Vijay Vazirani got his Bachelor’s degree in Computer Science from MIT in 1979 and his Ph.D. from the University of California at Berkeley in 1983. His research career has been centered around the design of algorithms and computational complexity theory. He has made seminal contributions to the classical maximum matching problem, approximation algorithms and the computability of equilibria, particularly algorithms for computing market equilibria. His work in complexity theory includes the Valiant-Vazirani theorem, proving that if UNIQUE-SAT is in P then NP = RP.

In 2001 he published what was widely regarded as the definitive book on Approximation Algorithms. This book has been translated into Japanese, Polish, French and Chinese. He was a Distinguished SISL Visitor at the Social and Information Sciences Laboratory at Caltech during 2011-12. He is a Guggenheim Fellow and an ACM Fellow.

Abstract

Profound insights, obtained over the last decade, have elevated equilibrium computation to a full-fledged area within the theory of algorithms and computational complexity. It has its own character which is quite distinct from the computability of optimization problems.

Using the powerful notions of complementarity and complementary pivot algorithms, traditional complexity classes NP, co-NP, ETR (Existential Theory of Reals) and UTR (Universal Theory of Reals), and new classes PPAD and FIXP, we will provide a broad overview of this theory as it stands today. The picture is intensely beautiful! The area still has low-hanging fruit -- we will indicate where.

Web Accessibility