TY - JOUR
T1 - On Communication Complexity of Fixed Point Computation
AU - Ganor, Anat
AU - Karthik, C. S.
AU - Pálvölgyi, Dömötör
N1 - Funding Information:
Anat Ganor received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 740282). Karthik C. S. was supported by Irit Dinur’s ERC-CoG grant 772839. Dömötör Pálvölgyi was supported by the Lendület program of the Hungarian Academy of Sciences (MTA), under grant number LP2017-19/2017. Authors’ addresses: A. Ganor, Rothberg building, School of Computer Science and Engineering, Hebrew University of Jerusalem, Jerusalem 9190401, Israel; email: anat.ganor@gmail.com; Karthik C. S., Weizmann Institute of Science, 234 Herzl Street, Rehovot 7610001, Israel; email: karthik0112358@gmail.com; D. Pálvölgyi, Institute of Mathematics, Eötvös Loránd University (ELTE), Pázmány Péter sétány 1/C, Budapest H-1117, Hungary; email: dom@cs.elte.hu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2021 Association for Computing Machinery. 2167-8375/2021/10-ART25 $15.00 https://doi.org/10.1145/3485004
Publisher Copyright:
© 2021 Association for Computing Machinery.
PY - 2021/12
Y1 - 2021/12
N2 - 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.
AB - 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.
KW - Brouwer's fixed point theorem
KW - Nash equilibrium
KW - Sperner's lemma
KW - communication complexity
UR - http://www.scopus.com/inward/record.url?scp=85118632749&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85118632749&partnerID=8YFLogxK
U2 - 10.1145/3485004
DO - 10.1145/3485004
M3 - Article
AN - SCOPUS:85118632749
SN - 2167-8375
VL - 9
JO - ACM Transactions on Economics and Computation
JF - ACM Transactions on Economics and Computation
IS - 4
M1 - 3485004
ER -