Computing a Fixed Point of Contraction Maps in Polynomial Queries

Explore a 37-minute lecture by Yuhao Li from Columbia University on computing fixed points of contraction maps using polynomial queries. Delve into the connection between solving simple stochastic games and computing fixed points of contraction maps. Discover a query-efficient algorithm for computing these fixed points, which may suggest that contraction fixed point and simple stochastic game problems could be computationally tractable. Learn about the positive results of this research and their potential implications for long-standing open problems in computational complexity. Gain insights from the joint work of Xi Chen, Mihalis Yannakakis, and the speaker, presented as part of the Games and Equilibria in System Design and Analysis series at the Simons Institute.

Computing a fixed point of contraction maps in polynomial queries