Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Computing a Fixed Point of Contraction Maps in Polynomial Queries

Simons Institute via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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.

Syllabus

Computing a fixed point of contraction maps in polynomial queries

Taught by

Simons Institute

Reviews

Start your review of Computing a Fixed Point of Contraction Maps in Polynomial Queries

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.