Seminar 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.
 

Speaker’s biography:

Yuhao LI is a fourth-year PhD student in the theory group at Columbia University, advised by Professor Xi CHEN and Professor Rocco SERVEDIO. He also collaborates closely with Professor Toniann PITASSI and Professor Mihalis YANNAKAKIS. Before that, Yuhao got his B.Sc. degree in computer science from Peking University, advised by Professor Xiaotie DENG on algorithmic game theory. Yuhao is broadly interested in theoretical computer science and discrete mathematics, including complexity theory (TFNP, proof complexity, communication complexity), logic, automata theory, games, and combinatorics.