Speaker Christos Papadimitriou
Host Nikhil Devanur and Yuval Peres
Affiliation UC Berkeley
Date recorded 6 July 2010
Nash equilibrium, integer factorization, and stable configuration of a Hopfield net are examples of total functions, problems in NP that are guaranteed to always have solutions. Each such problem is an implicit existence theorem; consequently, total functions are categorized by the elementary argument involved in the proof of the theorem: Pigeonhole principle, parity argument, conservation of degree, or potential function (no other kinds are known...). We will survey this area, and introduce a new class, lower than those studied in the past, containing several problems that had resisted classification: The Shapley-Condon simple stochastic games, fixpoints of contraction maps, finding Nash equilibria in network games, and finding KKT points of polynomials. Interestingly, this new class is best understood in terms of real-valued functions.
©2010 Microsoft Corporation. All rights reserved.