{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:02Z","timestamp":1750307702548,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"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","award":["CCF-0845003"],"award-info":[{"award-number":["CCF-0845003"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2009,9]]},"abstract":"<jats:p>\n            We exhibit an explicit function\n            <jats:italic>f<\/jats:italic>\n            : {0, 1}\n            <jats:sup>n<\/jats:sup>\n            \u2192{0, 1} that can be computed by a nondeterministic number-on-forehead protocol communicating\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) bits, but that requires\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03a9(1)<\/jats:sup>\n            bits of communication for randomized number-on-forehead protocols with\n            <jats:italic>k<\/jats:italic>\n            \u2009=\u2009\n            <jats:italic>\u03b4<\/jats:italic>\n            \u00b7log\n            <jats:italic>n<\/jats:italic>\n            players, for any fixed\n            <jats:italic>\u03b4<\/jats:italic>\n            \u2009&lt;\u20091. Recent breakthrough results for the Set-Disjointness function [Lee and Shraibman 2008; Chattopadhyay and Ada 2008] based on the work of Sherstov [2009; 2008a] imply such a separation but only when the number of players is\n            <jats:italic>k<\/jats:italic>\n            \u2009&lt;\u2009loglog\n            <jats:italic>n<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            We also show that for any\n            <jats:italic>k<\/jats:italic>\n            \u2009=\u2009\n            <jats:italic>A<\/jats:italic>\n            \u00b7loglog\n            <jats:italic>n<\/jats:italic>\n            the above function\n            <jats:italic>f<\/jats:italic>\n            is computable by a small circuit whose depth is constant whenever\n            <jats:italic>A<\/jats:italic>\n            is a (possibly large) constant. Recent results again give such functions but only when the number of players is\n            <jats:italic>k<\/jats:italic>\n            \u2009&lt;\u2009loglog\n            <jats:italic>n<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/1595391.1595392","type":"journal-article","created":{"date-parts":[[2009,11,30]],"date-time":"2009-11-30T14:56:36Z","timestamp":1259592996000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Improved Separations between Nondeterministic and Randomized Multiparty Communication"],"prefix":"10.1145","volume":"1","author":[{"given":"Matei","family":"David","sequence":"first","affiliation":[{"name":"University of Toronto"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[{"name":"University of Toronto"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[{"name":"Northeastern University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.15"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90047-M"},{"volume-title":"Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP). Springer, 134--145","author":"Beame P.","key":"e_1_2_1_4_1","unstructured":"Beame , P. , David , M. , Pitassi , T. , and Woelfel , P . 2007. Separating deterministic from nondeterministic not multiparty communication complexity . In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP). Springer, 134--145 . Beame, P., David, M., Pitassi, T., and Woelfel, P. 2007. Separating deterministic from nondeterministic not multiparty communication complexity. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP). Springer, 134--145."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Beame P. and Huynh-Ngoc D.-T. 2008a. Multiparty communication complexity and threshold size of AC 0. Manuscript. http:\/\/www.cs.washington.edu\/homes\/beame\/papers\/multiac0.pdf.  Beame P. and Huynh-Ngoc D.-T. 2008a. Multiparty communication complexity and threshold size of AC 0 . Manuscript. http:\/\/www.cs.washington.edu\/homes\/beame\/papers\/multiac0.pdf.","DOI":"10.1109\/FOCS.2009.12"},{"key":"e_1_2_1_6_1","unstructured":"Beame P. and Huynh-Ngoc D.-T. 2008b. Multiparty communication complexity of AC 0. Tech. rep. TR08-061 Electronic Colloquium on Computational Complexity. www.eccc.uni-trier.de\/.  Beame P. and Huynh-Ngoc D.-T. 2008b. Multiparty communication complexity of AC 0 . Tech. rep. TR08-061 Electronic Colloquium on Computational Complexity. www.eccc.uni-trier.de\/."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/060654645"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00131-2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808737"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.24"},{"key":"e_1_2_1_11_1","unstructured":"Chattopadhyay A. and Ada A. 2008. Multiparty communication complexity of disjointness. Tech. rep. TR08-002 Electronic Colloquium on Computational Complexity.  Chattopadhyay A. and Ada A. 2008. Multiparty communication complexity of disjointness. Tech. rep. TR08-002 Electronic Colloquium on Computational Complexity."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90015-0"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0406009"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_94"},{"volume-title":"Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM). Springer, 381--392","author":"Gutfreund D.","key":"e_1_2_1_15_1","unstructured":"Gutfreund , D. and Viola , E . 2004. Fooling parity tests with parity gates . In Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM). Springer, 381--392 . Gutfreund, D. and Viola, E. 2004. Fooling parity tests with parity gates. In Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM). Springer, 381--392."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01272517"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_55"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Kushilevitz E. and Nisan N. 1997. Communication Complexity. Cambridge University Press Cambridge UK.   Kushilevitz E. and Nisan N. 1997. Communication Complexity . Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.29"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90257-T"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222016"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129758"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001602"},{"key":"e_1_2_1_27_1","first-page":"145","article-title":"Quantum communication complexity of symmetric predicates. Izvestiya","volume":"67","author":"Razborov A.","year":"2003","unstructured":"Razborov , A. 2003 . Quantum communication complexity of symmetric predicates. Izvestiya : Mathematics 67 , 1, 145 -- 159 . Razborov, A. 2003. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics 67, 1, 145--159.","journal-title":"Mathematics"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90041-7"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374392"},{"key":"e_1_2_1_30_1","first-page":"59","article-title":"Communication lower bounds using dual polynomials","volume":"95","author":"Sherstov A.","year":"2008","unstructured":"Sherstov , A. 2008 b. Communication lower bounds using dual polynomials . Bull. EATCS 95 , 59 -- 93 . Sherstov, A. 2008b. Communication lower bounds using dual polynomials. Bull. EATCS 95, 59--93.","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/08071421X"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a007"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1595391.1595392","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1595391.1595392","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:03Z","timestamp":1750253403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1595391.1595392"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["10.1145\/1595391.1595392"],"URL":"https:\/\/doi.org\/10.1145\/1595391.1595392","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2009,9]]},"assertion":[{"value":"2008-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}