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.

• Admission

Tencent Meeting ID: 428-755-251