Title: Computing a Fixed Point of Contraction Maps in Polynomial Queries

Speaker: Mihalis Yannakakis (Percy K. and Vida L. W. Hudson Professor of Computer Science, Columbia University, USA)

Abstract:
We give an algorithm for finding an approximate fixed point of a contraction map under the L-infinity norm in polynomial number of queries;  specifically in O( k log(1/epsilon)) queries, where k is the dimension and epsilon is the approximation error.

Joint work with Xi Chen and Yuhao Li.

Short 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 at Avaya Labs, and Professor of Computer Science at Stanford University. Dr. Yannakakis received his PhD from Princeton University in 1979. His research interests include algorithms, complexity, optimization, game theory, databases, testing and verification. He is a recipient of the Knuth Prize, the INFORMS John von Neumann Theory Prize, the EATCS Award, he is a member of the National Academy of Engineering, the National Academy of Sciences, the American Academy of Arts and Sciences, Academia Europaea, a Fellow of the ACM, and a Bell Labs Fellow.