{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:34Z","timestamp":1763468074453,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"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":[[2012,5,19]]},"DOI":"10.1145\/2213977.2214026","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"525-548","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["The multiparty communication complexity of set disjointness"],"prefix":"10.1145","author":[{"given":"Alexander A.","family":"Sherstov","sequence":"first","affiliation":[{"name":"University of California, Los Angeles, Los Angeles, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_2_1_1","DOI":"10.1109\/SFCS.1989.63538"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_2_1","DOI":"10.1145\/22145.22192"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_3_1","DOI":"10.1109\/SFCS.1986.15"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_4_1","DOI":"10.1007\/s004930100009"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_5_1","DOI":"10.1016\/0022-0000(88)90028-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_6_1","DOI":"10.1016\/0022-0000(92)90047-M"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_7_1","DOI":"10.1016\/j.jcss.2003.11.006"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_8_1","DOI":"10.1145\/502090.502097"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_9_1","DOI":"10.5555\/2394539.2394558"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_10_1","DOI":"10.4086\/toc.2010.v006a009"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_11_1","DOI":"10.5555\/1747597.1748023"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_12_1","DOI":"10.1137\/060654645"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_13_1","DOI":"10.1007\/s00037-007-0220-2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_14_1","DOI":"10.1109\/FOCS.2008.45"},{"key":"e_1_3_2_2_15_1","volume-title":"Multiplayer XOR games and quantum communication complexity with clique-wise entanglement. Manuscript at http:\/\/arxiv.org\/abs\/0911.4007","author":"Briet J.","year":"2009","unstructured":"J. Briet , H. Buhrman , T. Lee , and T. Vidick . Multiplayer XOR games and quantum communication complexity with clique-wise entanglement. Manuscript at http:\/\/arxiv.org\/abs\/0911.4007 , 2009 . J. Briet, H. Buhrman, T. Lee, and T. Vidick. Multiplayer XOR games and quantum communication complexity with clique-wise entanglement. Manuscript at http:\/\/arxiv.org\/abs\/0911.4007, 2009."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_16_1","DOI":"10.1145\/800061.808737"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_17_1","DOI":"10.1109\/FOCS.2007.24"},{"key":"e_1_3_2_2_19_1","volume-title":"Electronic Colloquium on Computational Complexity (ECCC)","author":"Chattopadhyay A.","year":"2008","unstructured":"A. Chattopadhyay and A. Ada . Multiparty communication complexity of disjointness . In Electronic Colloquium on Computational Complexity (ECCC) , January 2008 . Report TR08-002. A. Chattopadhyay and A. Ada. Multiparty communication complexity of disjointness. In Electronic Colloquium on Computational Complexity (ECCC), January 2008. Report TR08-002."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_20_1","DOI":"10.1137\/0217015"},{"key":"e_1_3_2_2_21_1","volume-title":"Electronic Colloquium on Computational Complexity (ECCC)","author":"David M.","year":"2008","unstructured":"M. David and T. Pitassi . Separating NOF communication complexity classes $\\mathsfRP$ and $\\mathsfNP$ . In Electronic Colloquium on Computational Complexity (ECCC) , February 2008 . Report TR08-014. M. David and T. Pitassi. Separating NOF communication complexity classes $\\mathsfRP$ and $\\mathsfNP$. In Electronic Colloquium on Computational Complexity (ECCC), February 2008. Report TR08-014."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_22_1","DOI":"10.1145\/1595391.1595392"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_23_1","DOI":"10.4086\/toc.2010.v006a010"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_24_1","DOI":"10.1006\/inco.1994.1051"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_25_1","DOI":"10.1007\/BF01272517"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_26_1","DOI":"10.1145\/1374376.1374462"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_27_1","DOI":"10.1137\/0405044"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_28_1","DOI":"10.5555\/874063.875559"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_29_1","DOI":"10.1109\/CCC.2003.1214415"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_30_1","DOI":"10.1145\/1806689.1806702"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_31_1","DOI":"10.1137\/05063235X"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_32_1","DOI":"10.1016\/S0304-3975(96)00019-9"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_33_1","DOI":"10.5555\/264772"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_34_1","DOI":"10.1109\/CCC.2009.24"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_35_1","DOI":"10.1007\/s00037-009-0276-2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_36_1","DOI":"10.1002\/rsa.v34:3"},{"key":"e_1_3_2_2_37_1","volume-title":"Perceptrons: An Introduction to Computational Geometry","author":"Minsky M. L.","year":"1969","unstructured":"M. L. Minsky and S. A. Papert . Perceptrons: An Introduction to Computational Geometry . MIT Press , Cambridge, Mass ., 1969 . M. L. Minsky and S. A. Papert. Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge, Mass., 1969."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_38_1","DOI":"10.1007\/BF01263419"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_39_1","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_3_2_2_40_1","first-page":"145","article-title":"Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences","volume":"67","author":"Razborov A. A.","year":"2002","unstructured":"A. A. Razborov . Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences , Mathematics , 67 : 145 -- 159 , 2002 . A. A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences, Mathematics, 67:145--159, 2002.","journal-title":"Mathematics"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_41_1","DOI":"10.1016\/0020-0190(93)90041-7"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_42_1","DOI":"10.1145\/1374376.1374392"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_43_1","DOI":"10.1137\/08071421X"},{"key":"e_1_3_2_2_44_1","volume-title":"On quantum-classical equivalence for composed communication problems. Quantum Information & Computation, 10(5--6):435--455","author":"Sherstov A. A.","year":"2010","unstructured":"A. A. Sherstov . On quantum-classical equivalence for composed communication problems. Quantum Information & Computation, 10(5--6):435--455 , 2010 . A. A. Sherstov. On quantum-classical equivalence for composed communication problems. Quantum Information & Computation, 10(5--6):435--455, 2010."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_45_1","DOI":"10.1145\/1993636.1993643"},{"key":"e_1_3_2_2_46_1","volume-title":"Quantum communication complexity of block-composed functions. Quantum Information & Computation, 9(5--6):444--460","author":"Shi Y.","year":"2009","unstructured":"Y. Shi and Y. Zhu . Quantum communication complexity of block-composed functions. Quantum Information & Computation, 9(5--6):444--460 , 2009 . Y. Shi and Y. Zhu. Quantum communication complexity of block-composed functions. Quantum Information & Computation, 9(5--6):444--460, 2009."},{"key":"e_1_3_2_2_47_1","volume-title":"McGill University","author":"Tesson P.","year":"2003","unstructured":"P. Tesson . Computational complexity questions related to finite monoids and semigroups. PhD thesis , McGill University , 2003 . P. Tesson. Computational complexity questions related to finite monoids and semigroups. PhD thesis, McGill University, 2003."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_48_1","DOI":"10.1137\/050640941"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_49_1","DOI":"10.1007\/s00493-009-2667-z"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_50_1","DOI":"10.1145\/800135.804414"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_51_1","DOI":"10.1109\/FSCS.1990.89583"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC'12","name":"STOC'12: Symposium on Theory of Computing","location":"New York New York USA"},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214026","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2214026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:54Z","timestamp":1750238454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":50,"alternative-id":["10.1145\/2213977.2214026","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2214026","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}