# On Communication Complexity of Fixed Point Computation

arXiv: https://arxiv.org/abs/1909.10958 · HTML: https://mlsanity.com/paper/1909.10958/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Sep 2019.

## Built on by (most cited first, 1 of 1)

- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)

## Abstract (arXiv)

Brouwer's fixed point theorem states that any continuous function from a compact convex space to itself has a fixed point. Roughgarden and Weinstein (FOCS 2016) initiated the study of fixed point computation in the two-player communication model, where each player gets a function from [0,1]n to [0,1]n, and their goal is to find an approximate fixed point of the composition of the two functions. They left it as an open question to show a lower bound of 2Omega(n) for the (randomized) communication complexity of this problem, in the range of parameters which make it a total search problem. We answer this question affirmatively. Additionally, we introduce two natural fixed point problems in the two-player communication model. bullet Each player is given a function from [0,1]n to [0,1]n/2, and their goal is to find an approximate fixed point of the concatenation of the functions. bullet Each player is given a function from [0,1]n to [0,1]n, and their goal is to find an approximate fixed point of the interpolation of the functions. We show a randomized communication complexity lower bound of 2Omega(n) for these problems (for some constant approximation factor). Finally, we initiate the study of finding a panchromatic simplex in a Sperner-coloring of a triangulation (guaranteed by Sperner's lemma) in the two-player communication model: A triangulation T of the d-simplex is publicly known and one player is given a set SAsubset T and a coloring function from SA to 0,ldots ,d/2, and the other player is given a set SBsubset T and a coloring function from SB to d/2+1,ldots ,d, such that SAdotcup SB=T, and their goal is to find a panchromatic simplex. We show a randomized communication complexity lower bound of |T|Omega(1) for the aforementioned problem as well (when d is large).