CS Peer Talk | Computing a Fixed Point of Contraction Maps...

第四十五期

报告人：Yuhao Li, Columbia University

时间：8月6日（星期二）10:00am

方式：#腾讯会议：428-755-251

Host：李宁远，图灵班2019级

报告信息

Title

Computing a Fixed Point of Contraction Maps in Polynomial Queries

Abstract

It is well known that solving simple stochastic games, whose complexity remains a long-standing open problem, can be reduced to computing a fixed point of contraction maps. In this talk, we consider general algorithms that access the contraction map in a black-box manner (as an oracle). We show a positive result -- a query-efficient algorithm for computing a fixed point of contraction maps, which may be interpreted as evidence supporting that contraction fixed point/simple stochastic games might be computationally tractable. Joint work with Xi Chen and Mihalis Yannakakis.

Biography

Yuhao Li is a third-year PhD student in the theory group at Columbia University, advised by Xi Chen and Rocco Servedio. Prior to that, he got the B.Sc. degree in computer science from Peking University, advised by Xiaotie Deng on algorithmic game theory. He is broadly interested in theoretical computer science and discrete mathematics, including complexity theory (TFNP, communication complexity, proof complexity), logic and automata, games, and combinatorics.

about CS Peer Talk

作为活动的发起人，我们来自北京大学图灵班科研活动委员会，主要由图灵班各年级同学组成。我们希望搭建一个CS同学交流的平台，促进同学间的交流合作，帮助同学练习展示，同时增进友谊。

目前在计划中的系列包括但不限于：

教程系列：学生讲者为主，介绍自己的研究领域

研究系列：学生讲者为主，介绍自己的研究成果

客座系列：邀请老师做主题报告

除非报告人特别要求，报告默认是非公开的，希望营造一个自由放松但又互相激励的交流氛围。