On Communication Complexity of Fixed Point Computation

Anat Ganor, C. S. Karthik, Dömötör Pálvölgyi

Research output: Contribution to journalArticlepeer-review

Abstract

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 to , 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 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 to , and their goal is to find an approximate fixed point of the concatenation of the functions.Each player is given a function from to , and their goal is to find an approximate fixed point of the mean of the functions. We show a randomized communication complexity lower bound of 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 of the-simplex is publicly known and one player is given a set and a coloring function from to , and the other player is given a set and a coloring function from to , such that , and their goal is to find a panchromatic simplex. We show a randomized communication complexity lower bound of for the aforementioned problem as well (when is large). On the positive side, we show that if then there is a deterministic protocol for the Sperner problem with bits of communication.

Original languageEnglish (US)
Article number3485004
JournalACM Transactions on Economics and Computation
Volume9
Issue number4
DOIs
StatePublished - Dec 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Statistics and Probability
  • Economics and Econometrics
  • Marketing
  • Computational Mathematics

Keywords

  • Brouwer's fixed point theorem
  • communication complexity
  • Nash equilibrium
  • Sperner's lemma

Fingerprint

Dive into the research topics of 'On Communication Complexity of Fixed Point Computation'. Together they form a unique fingerprint.

Cite this