[Colloq] Theory of Computation Seminar - FRIDAY, OCTOBER 1 at 2:00pm

[Rachel Kalweit]

The College of Computer and INformation Science presents:

Theory of Computation Seminar

Costis Daskalakis
MIT                         

On Friday, October 1 at 2:00 Costis Daskalakis  will speak on,
"Geometrically Embedded Local Search."

The talk will take place at Northeastern
in room 366 of West Village H.

------------------------------------------------------------------

Abstract:

Recent work has shown that finding a mixed Nash equilibrium in normal
form games is PPAD-complete, while the pure Nash equilibrium problem in
selfish routing games is PLS-complete. On the other hand, there are
important classes of games, e.g. simple stochastic games, and fixed
point problems, e.g. fixed points of contraction maps, that appear
easier. For these problems the PPAD and PLS machinery seems inadequate
to provide an accurate complexity theoretic characterization; at the
same time, polynomial-time algorithms have been evading researchers for
decades. We provide complexity theoretic machinery that could lead to
completeness results at the interface of PPAD and PLS, in the form of
geometrically embedded local search. We also survey background results
on the complexity of Nash equilibria and Brouwer fixed points.


Host: Emanuele Viola