{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T16:02:42Z","timestamp":1725897762322},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_2","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T17:20:21Z","timestamp":1340385621000},"page":"13-24","source":"Crossref","is-referenced-by-count":2,"title":["The NOF Multiparty Communication Complexity of Composed Functions"],"prefix":"10.1007","author":[{"given":"Anil","family":"Ada","sequence":"first","affiliation":[]},{"given":"Arkadev","family":"Chattopadhyay","sequence":"additional","affiliation":[]},{"given":"Omar","family":"Fawzi","sequence":"additional","affiliation":[]},{"given":"Phuong","family":"Nguyen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Ada, A., Chattopadhyay, A., Fawzi, O., Nguyen, P.: The NOF Multiparty Communication Complexity of Composed Functions. Technical report, In Electronic Colloquium on Computational Complexity (ECCC) TR11\u2013155 (2011)","DOI":"10.1007\/978-3-642-31594-7_2"},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1137\/S0097539700375944","volume":"33","author":"L. Babai","year":"2004","unstructured":"Babai, L., G\u00e1l, A., Kimmel, P.G., Lokam, S.V.: Communication complexity of simultaneous messages. SIAM Journal on Computing\u00a033, 137\u2013166 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"2_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/3-540-59042-0_88","volume-title":"STACS 95","author":"L. Babai","year":"1995","unstructured":"Babai, L., Kimmel, P.G., Lokam, S.V.: Simultaneous Messages vs. Communication. In: Mayr, E.W., Puech, C. (eds.) STACS 1995. LNCS, vol.\u00a0900, pp. 361\u2013372. Springer, Heidelberg (1995)"},{"issue":"2","key":"2_CR4","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/0022-0000(92)90047-M","volume":"45","author":"L. Babai","year":"1992","unstructured":"Babai, L., Nisan, N., Szegedy, M.: Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. Syst. Sci.\u00a045(2), 204\u2013232 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1109\/FOCS.2009.12","volume-title":"Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009","author":"P. Beame","year":"2009","unstructured":"Beame, P., Huynh-Ngoc, D.-T.: Multiparty communication complexity and threshold circuit size of AC 0. In: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 53\u201362. IEEE Computer Society, Washington, DC (2009)"},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/BF01263423","volume":"4","author":"R. Beigel","year":"1994","unstructured":"Beigel, R., Tarui, J.: On ACC. Computational Complexity\u00a04, 350\u2013366 (1994)","journal-title":"Computational Complexity"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1145\/800061.808737","volume-title":"Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC 1983","author":"A.K. Chandra","year":"1983","unstructured":"Chandra, A.K., Furst, M.L., Lipton, R.J.: Multi-party protocols. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC 1983, pp. 94\u201399. ACM, New York (1983)"},{"key":"2_CR8","unstructured":"Chattopadhyay, A., Ada, A.: Multiparty communication complexity of disjointness. Technical report. In: Electronic Colloquium on Computational Complexity (ECCC) TR08\u2013002 (2008)"},{"issue":"1","key":"2_CR9","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1137\/0406009","volume":"6","author":"F.R.K. Chung","year":"1993","unstructured":"Chung, F.R.K., Tetali, P.: Communication complexity and quasi randomness. SIAM Journal on Discrete Mathematics\u00a06(1), 110\u2013123 (1993)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1006\/inco.1994.1051","volume":"112","author":"V. Grolmusz","year":"1994","unstructured":"Grolmusz, V.: The BNS lower bound for multi-party protocols is nearly optimal. Information and Computation\u00a0112, 51\u201354 (1994)","journal-title":"Information and Computation"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Grolmusz, V.: Separating the communication complexities of MOD m and MOD p circuits. In: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 278\u2013287 (1995)","DOI":"10.1006\/jcss.1995.1069"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1007\/BF01272517","volume":"1","author":"J. H\u00e5stad","year":"1991","unstructured":"H\u00e5stad, J., Goldmann, M.: On the power of small-depth threshold circuits. Computational Complexity\u00a01, 610\u2013618 (1991)","journal-title":"Computational Complexity"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge university press (1997)","DOI":"10.1017\/CBO9780511574948"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Lee, T., Schechtman, G., Shraibman, A.: Lower bounds on quantum multiparty communication complexity. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC), pp. 254\u2013262 (2009)","DOI":"10.1109\/CCC.2009.24"},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s00037-009-0276-2","volume":"18","author":"T. Lee","year":"2009","unstructured":"Lee, T., Shraibman, A.: Disjointness is hard in the multiparty number-on-the-forehead model. Computational Complexity\u00a018, 309\u2013336 (2009)","journal-title":"Computational Complexity"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/978-3-642-14165-2_41","volume-title":"Automata, Languages and Programming","author":"T. Lee","year":"2010","unstructured":"Lee, T., Zhang, S.: Composition Theorems in Communication Complexity. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 475\u2013489. Springer, Heidelberg (2010)"},{"key":"2_CR17","unstructured":"Pudl\u00e1k, P.: Personal communication (2006)"},{"issue":"2","key":"2_CR18","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/PL00001602","volume":"9","author":"R. Raz","year":"2000","unstructured":"Raz, R.: The BNS-Chung criterion for multi-party communication complexity. Computational Complexity\u00a09(2), 113\u2013122 (2000)","journal-title":"Computational Complexity"},{"issue":"1","key":"2_CR19","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1070\/IM2003v067n01ABEH000422","volume":"67","author":"A. Razborov","year":"2003","unstructured":"Razborov, A.: Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics\u00a067(1), 145\u2013159 (2003)","journal-title":"Izvestiya: Mathematics"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: The pattern matrix method for lower bounds on quantum communication. In: Proceedings of the 40th Symposium on Theory of Computing (STOC), pp. 85\u201394 (2007)","DOI":"10.1145\/1374376.1374392"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: The multiparty communication complexity of set disjointness. Technical report, In Electronic Colloquium on Computational Complexity (ECCC) TR11\u2013145 (2011)","DOI":"10.1145\/2213977.2214026"},{"key":"2_CR22","doi-asserted-by":"crossref","first-page":"255","DOI":"10.26421\/QIC9.3-4-5","volume":"9","author":"Y. Shi","year":"2009","unstructured":"Shi, Y., Zhang, Z.: Communication complexities of symmetric XOR functions. Quantum Information and Computation\u00a09, 255\u2013263 (2009)","journal-title":"Quantum Information and Computation"},{"key":"2_CR23","doi-asserted-by":"crossref","first-page":"444","DOI":"10.26421\/QIC9.5-6-7","volume":"9","author":"Y. Shi","year":"2009","unstructured":"Shi, Y., Zhu, Y.: Quantum communication complexity of block-composed functions. Quantum Information and Computation\u00a09, 444\u2013460 (2009)","journal-title":"Quantum Information and Computation"},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/800135.804414","volume-title":"Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing","author":"A.C. Yao","year":"1979","unstructured":"Yao, A.C.: Some complexity questions related to distributive computing (preliminary report). In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, pp. 209\u2013213. ACM Press, New York (1979)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T17:11:07Z","timestamp":1687540267000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}