Abstract

We study the query complexity of local search and Brouwer fixed-point computation when there are k rounds of interaction with the oracle that answers queries. Thus in each round, any number of simultaneous queries can be issued, the oracle answers are received, and then the queries for the next round are submitted. The algorithm must stop by the end of the k-th round. This model captures distributed settings, where each query is time consuming and can be executed by a separate processor to speed up computation time.
We present several new algorithms and lower bounds, which characterize the trade-off between the number of rounds of adaptivity and the total number of queries on local search and Brouwer fixed-point. We mainly focus on studying these problems on the d-dimensional grid [n]^d, where d is a constant.
Joint work with Simina Brânzei.

Biography

Jiawei Li, Turing Class. His research interests include complexity, algorithmic game theory, algorithm.

Admission: https://www.wjx.cn/vm/mUVXt1d.aspx

Online Talk: https://meeting.tencent.com/s/G68LyMszLrF1