

2013/03/15, MC103, 15:30  16:30
Computation of Least Fixed Points
Mihalis
Yannakakis
, Columbia University
Area:
Discrete Math
Abstract:
Many problems from different areas can be formulated as problems of computing
a fixed point of a suitable function. For many of these problems, the function
in the fixed point formulation is monotone, and the objects we want to compute
are given by a specific fixed point, namely the least fixed point of the function.
Many models and problems from a broad variety of areas can be thus expressed as least fixed point
computation problems, including in particular the analysis of various probabilistic models,
problems in stochastic optimization, and games.
It turns out that for some classes of functions we can compute the least fixed point
in polynomial time and thus we can analyze efficiently several of these models,
while for others there are strong indications that they cannot be solved in polynomial time,
and for yet others the question remains open.
In this talk we will discuss progress in this area.
The talk is based on a series of works with Kousha Etessami and Alistair Stewart.
Mihalis Yannakakis is the Percy K. and Vida L. W. Hudson Professor of Computer Science at Columbia University.
Prior to joining Columbia, he was Director of the Computing Principles Research Department
at Bell Labs and at Avaya Labs, and Professor of Computer Science at Stanford University.
Dr. Yannakakis received his PhD from Princeton University.
His research interests include algorithms, complexity, optimization, game theory, databases, testing and verification.
He has served on the editorial boards of several journals, including as past editorinchief
of the SIAM Journal on Computing, and has 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 recipient of the Knuth Prize, a member of the National Academy of Engineering,
a Fellow of the ACM, and a Bell Labs Fellow.


