Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
Created page with "== 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...."
== 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
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
