CS Events

Distinguished Lecture Series

Probability, Recursion, and the Computation of Fixed Points


Download as iCal file

Monday, March 07, 2016, 10:30am


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 (or the greatest fixed point) of the function. Many models and problems from a variety of areas fit in this framework, including in particular the analysis of various probabilistic models,
especially models that combine recursion and probability, problems in stochastic optimization, and games. It turns out that for some classes of functions we can compute the 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.

Speaker: Mihalis Yannakakis


Mihalis Yannakakis is the Percy K. and Vida L. W. Hudson Professor of Computer Science at Columbia University. Prior to joining Columbia, he was Head of the Computing Principles Research Department at Bell Labs, and Professor of Computer Science at Stanfo

Location : Core A (Room 301)


Eric Allender

Event Type: Distinguished Lecture Series



Columbia University