{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:52:46Z","timestamp":1775281966012,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,10,16]],"date-time":"2021-10-16T00:00:00Z","timestamp":1634342400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["740282"],"award-info":[{"award-number":["740282"]}]},{"name":"Irit Dinur\u2019s ERC-CoG","award":["772839"],"award-info":[{"award-number":["772839"]}]},{"DOI":"10.13039\/501100003825","name":"Hungarian Academy of Sciences","doi-asserted-by":"crossref","award":["LP2017-19\/2017"],"award-info":[{"award-number":["LP2017-19\/2017"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"\n Brouwer\u2019s 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\n \n [0,1]^n<\/jats:tex-math>\n <\/jats:inline-formula>\n to\n \n [0,1]^n<\/jats:tex-math>\n <\/jats:inline-formula>\n , and their goal is to find an approximate fixed point of the\n composition<\/jats:italic>\n of the two functions. They left it as an open question to show a lower bound of\n \n 2^{\\Omega (n)}<\/jats:tex-math>\n <\/jats:inline-formula>\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.\n <\/jats:p>\n \n Additionally, we introduce two natural fixed point problems in the two-player communication model.\n \n \n \n Each player is given a function from\n \n [0,1]^n<\/jats:tex-math>\n <\/jats:inline-formula>\n to\n \n [0,1]^{n\/2}<\/jats:tex-math>\n <\/jats:inline-formula>\n , and their goal is to find an approximate fixed point of the\n concatenation<\/jats:italic>\n of the functions.\n <\/jats:p>\n <\/jats:list-item>\n \n \n Each player is given a function from\n \n [0,1]^n<\/jats:tex-math>\n <\/jats:inline-formula>\n to\n \n [0,1]^{n}<\/jats:tex-math>\n <\/jats:inline-formula>\n , and their goal is to find an approximate fixed point of the\n mean<\/jats:italic>\n of the functions.\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n We show a randomized communication complexity lower bound of\n \n 2^{\\Omega (n)}<\/jats:tex-math>\n <\/jats:inline-formula>\n for these problems (for some constant approximation factor).\n <\/jats:p>\n \n \n Finally, we initiate the study of finding a panchromatic simplex in a Sperner-coloring of a triangulation (guaranteed by Sperner\u2019s lemma) in the two-player communication model: A triangulation\n \n T<\/jats:tex-math>\n <\/jats:inline-formula>\n of the\n \n d<\/jats:tex-math>\n <\/jats:inline-formula>\n -simplex is publicly known and one player is given a set\n \n S_A\\subset T<\/jats:tex-math>\n <\/jats:inline-formula>\n and a coloring function from\n \n S_A<\/jats:tex-math>\n <\/jats:inline-formula>\n to\n \n \\lbrace 0,\\ldots ,d\/2\\rbrace<\/jats:tex-math>\n <\/jats:inline-formula>\n , and the other player is given a set\n \n S_B\\subset T<\/jats:tex-math>\n <\/jats:inline-formula>\n and a coloring function from\n \n S_B<\/jats:tex-math>\n <\/jats:inline-formula>\n to\n \n \\lbrace d\/2+1,\\ldots ,d\\rbrace<\/jats:tex-math>\n <\/jats:inline-formula>\n , such that\n \n S_A\\dot{\\cup }S_B=T<\/jats:tex-math>\n <\/jats:inline-formula>\n , and their goal is to find a panchromatic simplex. We show a randomized communication complexity lower bound of\n \n |T|^{\\Omega (1)}<\/jats:tex-math>\n <\/jats:inline-formula>\n for the aforementioned problem as well (when\n \n d<\/jats:tex-math>\n <\/jats:inline-formula>\n is large). On the positive side, we show that if\n \n d\\le 4<\/jats:tex-math>\n <\/jats:inline-formula>\n then there is a deterministic protocol for the Sperner problem with\n \n O((\\log |T|)^2)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits of communication.\n <\/jats:p>","DOI":"10.1145\/3485004","type":"journal-article","created":{"date-parts":[[2021,10,17]],"date-time":"2021-10-17T02:06:47Z","timestamp":1634436407000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["On Communication Complexity of Fixed Point Computation"],"prefix":"10.1145","volume":"9","author":[{"given":"Anat","family":"Ganor","sequence":"first","affiliation":[{"name":"Hebrew University of Jerusalem, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karthik C.","family":"S.","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00f6m\u00f6t\u00f6r","family":"P\u00e1lv\u00f6lgyi","sequence":"additional","affiliation":[{"name":"Institute of Mathematics, E\u00f6tv\u00f6s Lor\u00e1nd University (ELTE), Budapest, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,10,16]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/1379866.1379868"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2908734"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055407"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456931"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1379759.1379761"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.052"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.14"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050008"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/11780342_12"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1128733"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/080720826"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/321978.321989"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9121-2"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1979.11994922"},{"key":"e_1_3_3_17_2","first-page":"12:1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA","author":"Ganor Anat","year":"2018","unstructured":"Anat Ganor and Karthik C. S.2018. 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. 12:1\u201312:16. https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2018.12"},{"key":"e_1_3_3_18_2","first-page":"847","volume-title":"Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014","author":"G\u00f6\u00f6s Mika","year":"2014","unstructured":"Mika G\u00f6\u00f6s and Toniann Pitassi. 2014. Communication lower bounds via critical block sensitivity. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. 847\u2013856. https:\/\/doi.org\/10.1145\/2591796.2591838"},{"key":"e_1_3_3_19_2","article-title":"Query-to-communication lifting for BPP","author":"G\u00f6\u00f6s Mika","year":"2017","unstructured":"Mika G\u00f6\u00f6s, Toniann Pitassi, and Thomas Watson. 2017. Query-to-communication lifting for BPP. Electronic Colloquium on Computational Complexity (ECCC) (2017). https:\/\/eccc.weizmann.ac.il\/report\/2017\/053\/.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_3_20_2","volume-title":"FOCS","author":"G\u00f6\u00f6s Mika","year":"2018","unstructured":"Mika G\u00f6\u00f6s and Aviad Rubinstein. 2018. Near-optimal communication lower bounds for approximate Nash equilibria. In FOCS."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00152-6"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.4169\/amer.math.monthly.118.09.777"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90017-4"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214000"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4068(98)00053-6"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.4064\/fm-22-1-77-108"},{"key":"e_1_3_3_28_2","unstructured":"Erica Klarreich. 2017. In Game Theory No Clear Path to Equilibrium. http:\/\/www.quantamagazine.org\/in-game-theory-no-clear-path-to-equilibrium-20170718\/. [Online; posted 18-July-2017]."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-016-1315-8"},{"key":"e_1_3_3_30_2","volume-title":"Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry","author":"Matousek Jiri","year":"2007","unstructured":"Jiri Matousek. 2007. Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Springer Publishing Company, Incorporated."},{"key":"e_1_3_3_31_2","first-page":"129","article-title":"An efficient randomized protocol for every Karchmer-Wigderson relation with two rounds","volume":"24","author":"Meir Or","year":"2017","unstructured":"Or Meir. 2017. An efficient randomized protocol for every Karchmer-Wigderson relation with two rounds. Electronic Colloquium on Computational Complexity (ECCC) 24 (2017), 129. https:\/\/eccc.weizmann.ac.il\/report\/2017\/129.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300014480"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_3_3_34_2","article-title":"Some games and machines for playing them","author":"Nash John","year":"1952","unstructured":"John Nash. 1952. Some games and machines for playing them. Rand Corp.Technical Report D-1164 (1952). https:\/\/www.rand.org\/content\/dam\/rand\/pubs\/documents\/2015\/D1164.pdf.","journal-title":"Rand Corp.Technical Report D-1164"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050062"},{"key":"e_1_3_3_37_2","article-title":"Complexity theory, game theory, and economics","author":"Roughgarden Tim","year":"2017","unstructured":"Tim Roughgarden. 2017. Complexity theory, game theory, and economics. Bellairs Research Institute of McGill University, Holetown, Barbados (February 2017). http:\/\/eccc.weizmann.ac.il\/report\/2018\/001\/.","journal-title":"Bellairs Research Institute of McGill University, Holetown, Barbados"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.32"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746578"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.35"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3185519"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02940617"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.2307\/2589747"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-66037-5"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1934-1501735-3"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485004","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485004","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:15Z","timestamp":1750191435000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485004"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,16]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3485004"],"URL":"https:\/\/doi.org\/10.1145\/3485004","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,16]]},"assertion":[{"value":"2020-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}