On Communication Complexity of Fixed Point Computation
share
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^Ω(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. ∙ 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. ∙ 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^Ω(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⊂ T and a coloring function from S_A to {0,... ,d/2}, and the other player is given a set S_B⊂ T and a coloring function from S_B to {d/2+1,... ,d}, such that S_A∪̇S_B=T, and their goal is to find a panchromatic simplex. We show a randomized communication complexity lower bound of |T|^Ω(1) for the aforementioned problem as well.
READ FULL TEXT
