publication . Preprint . Article . 2021

On Communication Complexity of Fixed Point Computation

Anat Ganor; C S Karthik; Dömötör Pálvölgyi;
Open Access English
  • Published: 31 Dec 2021
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 [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. 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 mean 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 \lbrace 0,\ldots ,d/2\rbrace , and the other player is given a set S_B\subset T and a coloring function from S_B to \lbrace d/2+1,\ldots ,d\rbrace , 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). On the positive side, we show that if d\le 4 then there is a deterministic protocol for the Sperner problem with O((\log |T|)^2) bits of communication.
Persistent Identifiers

doi: 10.1145/3485004

Subjects
ACM Computing Classification System: ComputingMethodologies_DOCUMENTANDTEXTPROCESSINGComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATIONMathematicsofComputing_GENERALTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
free text keywords: Computer Science - Computational Complexity, Computer Science - Computational Geometry, Computer Science - Computer Science and Game Theory, Computational Mathematics, Marketing, Economics and Econometrics, Statistics and Probability, Computer Science (miscellaneous), Fixed point, Communication complexity, Computer science, Upper and lower bounds, Function (mathematics), Discrete mathematics, Sperner's lemma, Fixed-point theorem, Search problem, Triangulation (social science)
Related Organizations
Funded by
EC| COMPECON
Project
COMPECON
Complexity and Simplicity in Economic Mechanisms
  • Funder: European Commission (EC)
  • Project Code: 740282
  • Funding stream: H2020 | ERC | ERC-ADG
Download fromView all 2 versions
Open Access
arXiv.org e-Print Archive
Preprint . 2019
Providers: arXiv.org e-Print Archive
null
ACM Transactions on Economics and Computation
Article . 2021
Providers: Crossref
19 references, page 1 of 2

[CDT09] Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player nash equilibria. J. ACM, 56(3), 2009.

Computational Complexity, 7(2):163{173, 1998.

Xi Chen and Shang-Hua Teng. Paths beyond local search: A tight bound for randomized xed-point computation. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 124{134, 2007.

[Dan06] Stefan S. Dantchev. On the complexity of the sperner lemma. In Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006, Proceedings, pages 115{124, 2006.

Shimon Even and Robert Endre Tarjan. A combinatorial problem which is complete in polynomial space. J. ACM, 23(4):710{719, 1976.

Kousha Etessami and Mihalis Yannakakis. On the complexity of nash equilibria and other xed points. SIAM J. Comput., 39(6):2531{2597, 2010. [OpenAIRE]

[FISV09] Katalin Friedl, Gabor Ivanyos, Miklos Santha, and Yves F. Verhoeven. On the blackbox complexity of sperner's lemma. Theory Comput. Syst., 45(3):629{646, 2009.

David Gale. The game of hex and brouwer xed-point theorem. The American Mathematical Monthly, 86(10):818{827, 1979.

Anat Ganor and Karthik C. S. Communication complexity of correlated equilibrium with small support. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA, pages 12:1{12:16, 2018.

Mika Goos and Toniann Pitassi. Communication lower bounds via critical block sensitivity. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 847{856, 2014.

Mika Goos and Aviad Rubinstein. Near-optimal communication lower bounds for approximate nash equilibria. In FOCS, 2018.

[HPV89] Michael D. Hirsch, Christos H. Papadimitriou, and Stephen A. Vavasis. Exponential lower bounds for nding brouwer x points. J. Complexity, 5(4):379{416, 1989.

Hossein Jowhari, Mert Saglam, and Gabor Tardos. Tight bounds for lp samplers, nding duplicates in streams, and related problems. In Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece, pages 49{58, 2011.

Fundamenta Mathematicae, 22(1):77{108, 1934.

Erica Klarreich. In game theory, no clear path to equilibrium, July 2017. http://www.quantamagazine.org/in-game-theory-no-clear-path-to-equilibrium20170718/ [Online; posted 18-July-2017].

19 references, page 1 of 2
12 research outcomes, page 1 of 2
12 research outcomes, page 1 of 2
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 [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. 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 mean 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 \lbrace 0,\ldots ,d/2\rbrace , and the other player is given a set S_B\subset T and a coloring function from S_B to \lbrace d/2+1,\ldots ,d\rbrace , 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). On the positive side, we show that if d\le 4 then there is a deterministic protocol for the Sperner problem with O((\log |T|)^2) bits of communication.
Persistent Identifiers

doi: 10.1145/3485004

Subjects
ACM Computing Classification System: ComputingMethodologies_DOCUMENTANDTEXTPROCESSINGComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATIONMathematicsofComputing_GENERALTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
free text keywords: Computer Science - Computational Complexity, Computer Science - Computational Geometry, Computer Science - Computer Science and Game Theory, Computational Mathematics, Marketing, Economics and Econometrics, Statistics and Probability, Computer Science (miscellaneous), Fixed point, Communication complexity, Computer science, Upper and lower bounds, Function (mathematics), Discrete mathematics, Sperner's lemma, Fixed-point theorem, Search problem, Triangulation (social science)
Related Organizations
Funded by
EC| COMPECON
Project
COMPECON
Complexity and Simplicity in Economic Mechanisms
  • Funder: European Commission (EC)
  • Project Code: 740282
  • Funding stream: H2020 | ERC | ERC-ADG
Download fromView all 2 versions
Open Access
arXiv.org e-Print Archive
Preprint . 2019
Providers: arXiv.org e-Print Archive
null
ACM Transactions on Economics and Computation
Article . 2021
Providers: Crossref
19 references, page 1 of 2

[CDT09] Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player nash equilibria. J. ACM, 56(3), 2009.

Computational Complexity, 7(2):163{173, 1998.

Xi Chen and Shang-Hua Teng. Paths beyond local search: A tight bound for randomized xed-point computation. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 124{134, 2007.

[Dan06] Stefan S. Dantchev. On the complexity of the sperner lemma. In Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006, Proceedings, pages 115{124, 2006.

Shimon Even and Robert Endre Tarjan. A combinatorial problem which is complete in polynomial space. J. ACM, 23(4):710{719, 1976.

Kousha Etessami and Mihalis Yannakakis. On the complexity of nash equilibria and other xed points. SIAM J. Comput., 39(6):2531{2597, 2010. [OpenAIRE]

[FISV09] Katalin Friedl, Gabor Ivanyos, Miklos Santha, and Yves F. Verhoeven. On the blackbox complexity of sperner's lemma. Theory Comput. Syst., 45(3):629{646, 2009.

David Gale. The game of hex and brouwer xed-point theorem. The American Mathematical Monthly, 86(10):818{827, 1979.

Anat Ganor and Karthik C. S. Communication complexity of correlated equilibrium with small support. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA, pages 12:1{12:16, 2018.

Mika Goos and Toniann Pitassi. Communication lower bounds via critical block sensitivity. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 847{856, 2014.

Mika Goos and Aviad Rubinstein. Near-optimal communication lower bounds for approximate nash equilibria. In FOCS, 2018.

[HPV89] Michael D. Hirsch, Christos H. Papadimitriou, and Stephen A. Vavasis. Exponential lower bounds for nding brouwer x points. J. Complexity, 5(4):379{416, 1989.

Hossein Jowhari, Mert Saglam, and Gabor Tardos. Tight bounds for lp samplers, nding duplicates in streams, and related problems. In Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece, pages 49{58, 2011.

Fundamenta Mathematicae, 22(1):77{108, 1934.

Erica Klarreich. In game theory, no clear path to equilibrium, July 2017. http://www.quantamagazine.org/in-game-theory-no-clear-path-to-equilibrium20170718/ [Online; posted 18-July-2017].

19 references, page 1 of 2
12 research outcomes, page 1 of 2
12 research outcomes, page 1 of 2
graphPowered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue