{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:58:44Z","timestamp":1775282324287,"version":"3.50.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2014,12,17]],"date-time":"2014-12-17T00:00:00Z","timestamp":1418774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,12,17]]},"abstract":"<jats:p>\n            We study the set disjointness problem in the most powerful model of bounded-error communication, the\n            <jats:italic>k<\/jats:italic>\n            -party randomized number-on-the-forehead model. We show that set disjointness requires \u03a9(\u221an\/2\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            <jats:italic>k<\/jats:italic>\n            ) bits of communication, where\n            <jats:italic>n<\/jats:italic>\n            is the size of the universe. Our lower bound generalizes to quantum communication, where it is essentially optimal. Proving this bound was a longstanding open problem even in restricted settings, such as one-way classical protocols with\n            <jats:italic>k<\/jats:italic>\n            =4 parties [Wigderson 1997]. The proof contributes a novel technique for lower bounds on multiparty communication, based on directional derivatives of protocols over the reals.\n          <\/jats:p>","DOI":"10.1145\/2629334","type":"journal-article","created":{"date-parts":[[2014,12,19]],"date-time":"2014-12-19T13:38:51Z","timestamp":1418996331000},"page":"1-71","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Communication Lower Bounds Using Directional Derivatives"],"prefix":"10.1145","volume":"61","author":[{"given":"Alexander A.","family":"Sherstov","sequence":"first","affiliation":[{"name":"University of California, Los Angeles, CA"}]}],"member":"320","published-online":{"date-parts":[[2014,12,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013898304645"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63538"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22192"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.15"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930100009"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90047-M"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.55"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748023"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0220-2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.45"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00341-9"},{"key":"e_1_2_1_14_1","unstructured":"Jop Briet Harry Buhrman Troy Lee and Thomas Vidick. 2009. Multiplayer XOR games and quantum communication complexity with clique-wise entanglement. Manuscript. http:\/\/arxiv.org\/abs\/0911.4007.  Jop Briet Harry Buhrman Troy Lee and Thomas Vidick. 2009. Multiplayer XOR games and quantum communication complexity with clique-wise entanglement. Manuscript. http:\/\/arxiv.org\/abs\/0911.4007."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796493"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276713"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.18"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808737"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.24"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217015"},{"key":"e_1_2_1_23_1","volume-title":"Cusick and Pantelimon St\u0103nic\u0103","author":"Thomas","year":"2009","unstructured":"Thomas W. Cusick and Pantelimon St\u0103nic\u0103 . 2009 . Cryptographic Boolean Functions and Applications. Academic Press . Thomas W. Cusick and Pantelimon St\u0103nic\u0103. 2009. Cryptographic Boolean Functions and Applications. Academic Press."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2011.10.013"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a010"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0290-4"},{"key":"e_1_2_1_27_1","first-page":"1","article-title":"Finite field models in additive combinatorics. Surveys in Combinatorics","volume":"327","author":"Green Ben","year":"2005","unstructured":"Ben Green . 2005 . Finite field models in additive combinatorics. Surveys in Combinatorics , London Math. Soc. Lecture Notes 327 , 1 -- 27 . Ben Green. 2005. Finite field models in additive combinatorics. Surveys in Combinatorics, London Math. Soc. Lecture Notes 327, 1--27.","journal-title":"London Math. Soc. Lecture Notes"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0013091505000325"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1051"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01272517"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374462"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875559"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806702"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063235X"},{"key":"e_1_2_1_37_1","volume-title":"Communication Complexity","author":"Kushilevitz Eyal","unstructured":"Eyal Kushilevitz and Noam Nisan . 1997. Communication Complexity . Cambridge University Press . Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press."},{"key":"e_1_2_1_38_1","volume-title":"Yang","author":"Le Cam L.","year":"2000","unstructured":"L. Le Cam and Grace L . Yang . 2000 . Asymptotics in Statistics : Some Basic Concepts 2nd Ed. Springer . L. Le Cam and Grace L. Yang. 2000. Asymptotics in Statistics: Some Basic Concepts 2nd Ed. Springer."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.24"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0276-2"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v34:3"},{"key":"e_1_2_1_42_1","volume-title":"Papert","author":"Minsky Marvin L.","year":"1969","unstructured":"Marvin L. Minsky and Seymour A . Papert . 1969 . Perceptrons : An Introduction to Computational Geometry. MIT Press , Cambridge, MA. Marvin L. Minsky and Seymour A. Papert. 1969. Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_2_1_44_1","volume-title":"A User's Guide to Measure Theoretic Probability","author":"Pollard David","unstructured":"David Pollard . 2001. A User's Guide to Measure Theoretic Probability . Cambridge University Press . David Pollard. 2001. A User's Guide to Measure Theoretic Probability. Cambridge University Press."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/090747270"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_2_1_47_1","first-page":"145","article-title":"Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences","volume":"67","author":"Razborov Alexander A.","year":"2002","unstructured":"Alexander A. Razborov . 2002 . Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences , Mathematics 67 , 145 -- 159 . Alexander A. Razborov. 2002. Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences, Mathematics 67, 145--159.","journal-title":"Mathematics"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/08071421X"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214026"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993643"},{"key":"e_1_2_1_52_1","first-page":"5","article-title":"Quantum communication complexity of block-composed functions","volume":"9","author":"Shi Yaoyun","year":"2009","unstructured":"Yaoyun Shi and Yufan Zhu . 2009 . Quantum communication complexity of block-composed functions . Quant. Inf. Computat. 9 , 5 -- 6 , 444--460. Yaoyun Shi and Yufan Zhu. 2009. Quantum communication complexity of block-composed functions. Quant. Inf. Computat. 9, 5--6, 444--460.","journal-title":"Quant. Inf. Computat."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-2789(90)90174-N"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2667-z"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.95"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629334","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629334","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:30Z","timestamp":1750231170000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,17]]},"references-count":53,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,12,17]]}},"alternative-id":["10.1145\/2629334"],"URL":"https:\/\/doi.org\/10.1145\/2629334","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,17]]},"assertion":[{"value":"2013-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}