{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:09Z","timestamp":1750220529231,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":22,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451106","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1194-1207","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The communication complexity of multiparty set disjointness under product distributions"],"prefix":"10.1145","author":[{"given":"Nachum","family":"Dershowitz","sequence":"first","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rotem","family":"Oshman","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tal","family":"Roth","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_2_1_2_1","first-page":"1","article-title":"Robust Communication-Optimal Distributed Clustering Algorithms. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). 132","volume":"18","author":"Awasthi Pranjal","year":"2019","unstructured":"Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, and David P. Woodruff. 2019. Robust Communication-Optimal Distributed Clustering Algorithms. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). 132, Pages 18:1\u201318:16.","journal-title":"Pages"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_3_1","DOI":"10.1109\/SFCS.1986.15"},{"key":"e_1_3_2_1_4_1","first-page":"218","volume-title":"43rd Symposium on Foundations of Computer Science (FOCS","author":"Bar-Yossef Ziv","year":"2002","unstructured":"Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. 2002. An Information Statistics Approach to Data Stream and Communication Complexity. In 43rd Symposium on Foundations of Computer Science (FOCS 2002). Pages 209\u2013218."},{"key":"e_1_3_2_1_5_1","first-page":"544","article-title":"Correlation in Hard Distributions in Communication Complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Bottesch Ralph","year":"2015","unstructured":"Ralph Bottesch, Dmitry Gavinsky, and Hartmut Klauck. 2015. Correlation in Hard Distributions in Communication Complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM. LIPIcs. 40, Pages 544\u2013572.","journal-title":"APPROX\/RANDOM. LIPIcs. 40, Pages"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1109\/FOCS.2013.77"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.1145\/2767386.2767425"},{"key":"e_1_3_2_1_8_1","first-page":"155","volume-title":"Communication Tradeoff for Multi-Party Set Disjointness. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS","author":"Braverman Mark","year":"2017","unstructured":"Mark Braverman and Rotem Oshman. 2017. A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017. Pages 144\u2013155."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1145\/2611462.2611501"},{"key":"e_1_3_2_1_10_1","first-page":"278","volume-title":"Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity. In 42nd Annual Symposium on Foundations of Computer Science, FOCS","author":"Chakrabarti Amit","year":"2001","unstructured":"Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew Chi-Chih Yao. 2001. Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001. Pages 270\u2013278."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1145\/1855118.1855133"},{"key":"e_1_3_2_1_12_1","first-page":"3727","article-title":"Communication-Optimal Distributed Clustering","author":"Chen Jiecao","year":"2016","unstructured":"Jiecao Chen, He Sun, David Woodruff, and Qin Zhang. 2016. Communication-Optimal Distributed Clustering. In Advances in Neural Information Processing Systems. 29, Pages 3727\u20133735.","journal-title":"Advances in Neural Information Processing Systems. 29, Pages"},{"key":"e_1_3_2_1_13_1","first-page":"505","article-title":"Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness. In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009","author":"Gronemeier Andr\u00e9","year":"2009","unstructured":"Andr\u00e9 Gronemeier. 2009. Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness. In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009. LIPIcs. 3, Pages 505\u2013516.","journal-title":"LIPIcs. 3, Pages"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.1007\/s00446-020-00371-6"},{"key":"e_1_3_2_1_15_1","first-page":"573","volume-title":"12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009. Lecture Notes in Computer Science. 5687","author":"Jayram T. S.","year":"2009","unstructured":"T. S. Jayram. 2009. Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009. Lecture Notes in Computer Science. 5687, Pages 562\u2013573."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1137\/1.9781611973099.42"},{"doi-asserted-by":"crossref","unstructured":"Anup Rao and Amir Yehudayoff. 2020. Communication Complexity: and Applications.","key":"e_1_3_2_1_17_1","DOI":"10.1017\/9781108671644"},{"doi-asserted-by":"crossref","unstructured":"Alexander A Razborov. 1990. On the distributional complexity of disjointness. In International Colloquium on Automata Languages and Programming. Pages 249\u2013253.","key":"e_1_3_2_1_18_1","DOI":"10.1007\/BFb0032036"},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of the Second Annual Conference on Structure in Complexity Theory","author":"Schnitger Georg","year":"1987","unstructured":"Georg Schnitger and Bala Kalyanasundaram. 1987. The probabilistic communication complexity of set intersection. In Proceedings of the Second Annual Conference on Structure in Complexity Theory 1987."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1007\/978-3-662-44522-8_3"},{"key":"e_1_3_2_1_21_1","first-page":"960","volume-title":"Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing. STOC '12","author":"David","unstructured":"David P. Woodruff and Qin Zhang. 2012. Tight Bounds for Distributed Functional Monitoring. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing. STOC '12. Pages 941\u2013960."},{"volume-title":"When Distributed Computation Is Communication Expensive. In Distributed Computing: 27th International Symposium, DISC 2013. Pages 16\u201330","author":"David","unstructured":"David P. Woodruff and Qin Zhang. 2013. When Distributed Computation Is Communication Expensive. In Distributed Computing: 27th International Symposium, DISC 2013. Pages 16\u201330.","key":"e_1_3_2_1_22_1"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '21","name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451106","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":22,"alternative-id":["10.1145\/3406325.3451106","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451106","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}