Distinguished Lecture - Mihalis Yannakakis: Fixed Point Computation Problems and Facets of Complexity

Abstract: Many problems from a wide variety of areas can be formulated mathematically as the problem of computing a fixed point of a suitable given multivariate function. Examples include a variety of problems from game theory, economics, optimization, stochastic analysis, verification, and others. In some problems there is a unique fixed point (for example if the function is a contraction); in others there may be multiple fixed points and any one of them is an acceptable solution; while in other cases the desired object is a specific fixed point (for example the least fixed point or greatest fixed point of a monotone function). In this talk we will discuss several types of fixed point computation problems, their complexity, and some of the common themes that have emerged: classes of problems for which there are efficient algorithms, and other classes for which there seem to be serious obstacles.

Bio: 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 Stanford University. Dr. Yannakakis received his PhD from Princeton University. He has served on the editorial boards of several journals, including as the editor-in-chief of the SIAM Journal on Computing, and has chaired various conferences, including STOC, FOCS and PODS. Dr. Yannakakis is a recipient of the Knuth Prize, a member of the National Academy of Sciences, the National Academy of Engineering, and of Academia Europaea, a Fellow of the ACM, and a Bell Labs Fellow.

Coffee and cookies will be provided.