# On Communication Complexity of Fixed Point Computation

- Published: 31 Dec 2021

- Link this publication to...
- Cite this publication
Add to ORCID Please grant OpenAIRE to access and update your ORCID works.This research outcome is the result of merged research outcomes in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged research outcome.

doi: 10.1145/3485004

- Eötvös Loránd University Hungary
- Weizmann Institute of Science Israel
- Hebrew University of Jerusalem Israel

- Funder: European Commission (EC)
- Project Code: 740282
- Funding stream: H2020 | ERC | ERC-ADG

- 1
- 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].

- 1
- 2

- 1
- 2

- 2022 . IsAmongTopNSimilarDocuments
- 2022 . IsAmongTopNSimilarDocuments
- 2022 . IsAmongTopNSimilarDocuments
- 2021 . IsAmongTopNSimilarDocuments
- 2022 . IsAmongTopNSimilarDocuments
- 2022 . IsAmongTopNSimilarDocuments
- 2022 . IsAmongTopNSimilarDocuments

- 1
- 2

doi: 10.1145/3485004

- Eötvös Loránd University Hungary
- Weizmann Institute of Science Israel
- Hebrew University of Jerusalem Israel

- Funder: European Commission (EC)
- Project Code: 740282
- Funding stream: H2020 | ERC | ERC-ADG

- 1
- 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].

- 1
- 2

- 1
- 2

- 2022 . IsAmongTopNSimilarDocuments
- 2022 . IsAmongTopNSimilarDocuments
- 2022 . IsAmongTopNSimilarDocuments
- 2021 . IsAmongTopNSimilarDocuments
- 2022 . IsAmongTopNSimilarDocuments
- 2022 . IsAmongTopNSimilarDocuments
- 2022 . IsAmongTopNSimilarDocuments

- 1
- 2