October 27, 2009: Distinguished Lecturer Series - Mihalis Yannakakis: "Computational Aspects of Equilibria"

The University of Illinois at Chicago

Department of Computer Science

2008-2009 Distinguished Lecturer Seminar Series

Computational Aspects of Equilibria

Mihalis Yannakakis
Percy K. and Vida L. W. Hudson Professor
Department of Computer Science
Columbia University
Tuesday, November 10, 2009
11:00 a.m., SEO 1000


Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; price equilibria in markets; optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysis of the evolution of various types of dynamic stochastic models. It is not known whether these problems can be solved in polynomial time. Despite their broad diversity, there are certain common computational principles that underlie different types of equilibria and connect many of these problems to each other. In this talk we will discuss some of these common principles and the corresponding complexity classes that capture them; the effect on the complexity of the underlying computational framework; and the relationship with other open questions in computation.

Brief Bio:

Mihalis Yannakakis received the Diploma in Electrical Engineering from the National Technical University of Athens, Greece, in 1975, and the Ph.D. degree in Computer Science from Princeton University in 1979. He joined Bell Laboratories in 1978 where he worked until 2001, serving as Director of the Computing Principles Research Department since 1991. He joined Avaya Laboratories in July 2001, where he was the Director of Computing Principles Research during 2001-2002. He was a Professor of Computer Science at Stanford University during 2002-2003 and joined Columbia University in January 2004.

His research interests include algorithms and complexity, combinatorial optimization, databases, testing and verification. Dr. Yannakakis was the Editor-in-chief of the SIAM Journal on Computing 1998-2003and serves on the editorial boards of several other journals. He has served on the program committees and chaired various conferences, including the IEEE Symposium on Foundations of Computer Science, the ACM Symposium on Theory of Computing and the ACM Symposium on Principles of Database Systems. Dr. Yannakakis is a Fellow of the ACM, a Bell Labs Fellow and won the Donald E. Knuth Prize in 2005.

Host: Bhaskar DasGupta

You may view a video of the presentation here. If you would like to view the presentation in a Quicktime format please click here.

Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF