  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 $2^{\Omega(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 $2^{\Omega(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 $S_A\subset T$ and a coloring
function from $S_A$ to $\{0,\ldots ,d/2\}$, and the other player is given a set
$S_B\subset T$ and a coloring function from $S_B$ to $\{d/2+1,\ldots ,d\}$,
such that $S_A\dot\cup S_B=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).

Computational Complexity;Computational Geometry;Computer Science and Game Theory