Computing a fixed point of contraction maps in polynomial queries

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]