{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:05:07Z","timestamp":1781028307730,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"Swiss State Secretariat for Education, Research and Innovation (SERI)","award":["MB22.00026"],"award-info":[{"award-number":["MB22.00026"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800907","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"2030-2039","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Pseudodeterministic Communication Complexity"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-5095-7382","authenticated-orcid":false,"given":"Mika","family":"G\u00f6\u00f6s","sequence":"first","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0259-9355","authenticated-orcid":false,"given":"Nathaniel","family":"Harms","sequence":"additional","affiliation":[{"name":"University of British Columbia, Vancouver, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-8393-812X","authenticated-orcid":false,"given":"Artur","family":"Riazanov","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-8461-7123","authenticated-orcid":false,"given":"Anastasia","family":"Sofronova","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2809-3467","authenticated-orcid":false,"given":"Dmitry","family":"Sokolov","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"},{"name":"Universit\u00e9 de Montr\u00e9al, Montreal, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9149-1842","authenticated-orcid":false,"given":"Weiqiang","family":"Yuan","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","unstructured":"Hugo Aaronson Tom Gur and Jiawei Li. 2026. Pseudo-deterministic Quantum Algorithms. arXiv. https:\/\/doi.org\/10.48550\/arXiv.2602.17647 10.48550\/arXiv.2602.17647","DOI":"10.48550\/arXiv.2602.17647"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806711"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2024.1"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","unstructured":"Igor Balla Lianna Hambardzumyan and Istv\u00e1 Tomon. 2025. Factorization Norms and an Inverse Theorem for MaxCut. arXiv. https:\/\/doi.org\/10.48550\/arXiv.2506.23989 10.48550\/arXiv.2506.23989","DOI":"10.48550\/arXiv.2506.23989"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","unstructured":"Ari Blondal Hamed Hatami Pooya Hatami Chavdar Lalov and Sivan Tretiak. 2025. Borsuk-Ulam and replicable learning of large-margin halfspaces. arXiv. https:\/\/doi.org\/10.48550\/arXiv.2503.15294 10.48550\/arXiv.2503.15294","DOI":"10.48550\/arXiv.2503.15294"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2023.30"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00148"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2023.34"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1310153"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.14"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00074"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3532737.3532745"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718129"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(81)90009-1"},{"key":"e_1_3_2_1_15_1","unstructured":"Eran Gat and Shafi Goldwasser. 2011. Probabilistic search algorithms with unique answers and their cryptographic applications. Electronic Colloquium on Computational Complexity (ECCC). https:\/\/eccc.weizmann.ac.il\/report\/2011\/136\/"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.70010"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","unstructured":"Oded Goldreich. 2011. In a World of P=BPP. In Studies in Complexity and Cryptography. Springer Berlin Germany. 191\u2013232. https:\/\/doi.org\/10.1007\/978-3-642-22670-0_20 10.1007\/978-3-642-22670-0_20","DOI":"10.1007\/978-3-642-22670-0_20"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422453"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.79"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.36"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718155"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-018-0175-5"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2019.38"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M103145X"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M115339X"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-022-2365-8"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214000"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585187"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519973"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009656"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451085"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055500"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800907","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:54:36Z","timestamp":1781027676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800907"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":32,"alternative-id":["10.1145\/3798129.3800907","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800907","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}