On Communication Complexity of Fixed Point Computation

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).