  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.
  For local search, if the number of rounds $k$ is a constant, then we obtain a
query complexity of $\Theta\bigl(n^{\frac{d^{k+1} - d^k}{d^k - 1}}\bigl)$ for
both deterministic and randomized algorithms. On the other hand, when the
number of rounds is polynomial, i.e. of the form $n = k^{\alpha}$, where
$\alpha$ is a constant with $0 < \alpha < d/2$, we obtain an upper bound of
$O\left(n^{(d-1) - \frac{d-2}{d}\alpha}\right)$ and a lower bound of
$\widetilde{\Omega}\bigl(\max(n^{(d-1)-\alpha}, n^{\frac{d}{2}})\bigr)$ for
randomized algorithms. For Brouwer fixed-point, we have query complexity of
$\Theta\bigl(n^{\frac{d^{k+1} - d^k}{d^k - 1}}\bigl)$ for both deterministic
and randomized algorithm.
