{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:30:57Z","timestamp":1725517857163},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540853626"},{"type":"electronic","value":"9783540853633"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85363-3_30","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T15:29:28Z","timestamp":1219850968000},"page":"371-384","source":"Crossref","is-referenced-by-count":2,"title":["Improved Separations between Nondeterministic and Randomized Multiparty Communication"],"prefix":"10.1007","author":[{"given":"Matei","family":"David","sequence":"first","affiliation":[]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized algorithm for the maximal independent set problem. Journal of Algorithms\u00a07, 567\u2013583 (1986)","journal-title":"Journal of Algorithms"},{"key":"30_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/978-3-540-73420-8_14","volume-title":"Automata, Languages and Programming","author":"P. Beame","year":"2007","unstructured":"Beame, P., David, M., Pitassi, T., Woelfel, P.: Separating deterministic from nondet, nof multiparty communication complexity. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 134\u2013145. Springer, Heidelberg (2007)"},{"key":"30_CR3","first-page":"337","volume-title":"FOCS","author":"L. Babai","year":"1986","unstructured":"Babai, L., Frankl, P., Simon, J.: Complexity classes in communication complexity theory (preliminary version). In: FOCS, pp. 337\u2013347. IEEE, Los Alamitos (1986)"},{"issue":"2","key":"30_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. System Sci.\u00a045(2), 204\u2013232 (1992)","journal-title":"J. Comput. System Sci."},{"issue":"5","key":"30_CR5","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0020-0190(97)00131-2","volume":"63","author":"R.B. Boppana","year":"1997","unstructured":"Boppana, R.B.: The average sensitivity of bounded-depth circuits. Inform. Process. Lett.\u00a063(5), 257\u2013261 (1997)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"30_CR6","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/060654645","volume":"37","author":"P. Beame","year":"2007","unstructured":"Beame, P., Pitassi, T., Segerlind, N.: Lower bounds for lov\u00e1sz\u2013schrijver systems and beyond follow from multiparty communication complexity. SIAM J. Comput.\u00a037(3), 845\u2013869 (2007)","journal-title":"SIAM J. Comput."},{"key":"30_CR7","unstructured":"Chattopadhyay, A., Ada, A.: Multiparty communication complexity of disjointness. ECCC, Technical Report TR08-002 (2008)"},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Furst, M.L., Lipton, R.J.: Multi-party protocols. In: STOC (1983)","DOI":"10.1145\/800061.808737"},{"issue":"1","key":"30_CR9","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","volume":"5","author":"B. Chor","year":"1989","unstructured":"Chor, B., Goldreich, O.: On the power of two-point based sampling. Journal of Complexity\u00a05(1), 96\u2013106 (1989)","journal-title":"Journal of Complexity"},{"key":"30_CR10","first-page":"449","volume-title":"FOCS","author":"A. Chattopadhyay","year":"2007","unstructured":"Chattopadhyay, A.: Discrepancy and the power of bottom fan-in in depth-three circuits. In: FOCS, October 2007, pp. 449\u2013458. IEEE, Los Alamitos (2007)"},{"issue":"1","key":"30_CR11","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 J. Discrete Math.\u00a06(1), 110\u2013123 (1993)","journal-title":"SIAM J. Discrete Math."},{"key":"30_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1163","DOI":"10.1007\/11523468_94","volume-title":"Automata, Languages and Programming","author":"J. Ford","year":"2005","unstructured":"Ford, J., G\u00e1l, A.: Hadamard tensors and lower bounds on multiparty communication complexity. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1163\u20131175. Springer, Heidelberg (2005)"},{"key":"30_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/978-3-540-27821-4_34","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"D. Gutfreund","year":"2004","unstructured":"Gutfreund, D., Viola, E.: Fooling parity tests with parity gates. In: Jansen, K., Khanna, S., Rolim, J., Ron, D. (eds.) RANDOM 2004. LNCS, vol.\u00a03122, pp. 381\u2013392. Springer, Heidelberg (2004)"},{"issue":"2","key":"30_CR14","doi-asserted-by":"publisher","first-page":"113","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. Comput. Complexity\u00a01(2), 113\u2013129 (1991)","journal-title":"Comput. Complexity"},{"key":"30_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1007\/11672142_55","volume-title":"STACS 2006","author":"A. Healy","year":"2006","unstructured":"Healy, A., Viola, E.: Constant-depth circuits for arithmetic in finite fields of characteristic two. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 672\u2013683. Springer, Heidelberg (2006)"},{"key":"30_CR16","volume-title":"Communication complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, Cambridge (1997)"},{"issue":"3","key":"30_CR17","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transform, and learnability. J. Assoc. Comput. Mach.\u00a040(3), 607\u2013620 (1993)","journal-title":"J. Assoc. Comput. Mach."},{"key":"30_CR18","volume-title":"CCC","author":"T. Lee","year":"2008","unstructured":"Lee, T., Shraibman, A.: Disjointness is hard in the multi-party number on the forehead model. In: CCC. IEEE, Los Alamitos (2008)"},{"key":"30_CR19","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1145\/100216.100246","volume-title":"STOC","author":"Y. Mansour","year":"1990","unstructured":"Mansour, Y., Nisan, N., Tiwari, P.: The computational complexity of universal hashing. In: STOC, pp. 235\u2013243. ACM Press, New York (1990)"},{"issue":"4","key":"30_CR20","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput.\u00a022(4), 838\u2013856 (1993)","journal-title":"SIAM J. Comput."},{"key":"30_CR21","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Szegedy, M.: On the degree of boolean functions as real polynomials. Computational Complexity\u00a04, 301\u2013313 (1994)","journal-title":"Computational Complexity"},{"issue":"1","key":"30_CR22","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/0222016","volume":"22","author":"N. Nisan","year":"1993","unstructured":"Nisan, N., Wigderson, A.: Rounds in communication complexity revisited. SIAM J. Comput.\u00a022(1), 211\u2013219 (1993)","journal-title":"SIAM J. Comput."},{"key":"30_CR23","first-page":"468","volume-title":"STOC","author":"R. Paturi","year":"1992","unstructured":"Paturi, R.: On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In: STOC, pp. 468\u2013474. ACM, New York (1992)"},{"issue":"4","key":"30_CR24","first-page":"598","volume":"41","author":"A.A. Razborov","year":"1987","unstructured":"Razborov, A.A.: Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Mat. Zametki\u00a041(4), 598\u2013607, 623 (1987)","journal-title":"Mat. Zametki"},{"issue":"2","key":"30_CR25","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. Comput. Complexity\u00a09(2), 113\u2013122 (2000)","journal-title":"Comput. Complexity"},{"issue":"1","key":"30_CR26","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"},{"issue":"6","key":"30_CR27","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0020-0190(93)90041-7","volume":"45","author":"A. Razborov","year":"1993","unstructured":"Razborov, A., Wigderson, A.: $n\\sp {\\Omega(\\log n)}$ lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom. Inform. Process. Lett.\u00a045(6), 303\u2013307 (1993)","journal-title":"Inform. Process. Lett."},{"key":"30_CR28","doi-asserted-by":"crossref","unstructured":"Sherstov, A.: Separating AC0 from depth-2 majority circuits. In: STOC 2007: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (2007)","DOI":"10.1145\/1250790.1250834"},{"key":"30_CR29","doi-asserted-by":"crossref","unstructured":"Sherstov, A.: The pattern matrix method for lower bounds on quantum communication. In: STOC (2008)","DOI":"10.1145\/1374376.1374392"},{"key":"30_CR30","unstructured":"Sherstov, A.A.: Communication lower bounds using dual polynomials. Electronic Colloquium on Computational Complexity, Technical Report TR08-057 (2008)"},{"key":"30_CR31","volume-title":"CCC","author":"E. Viola","year":"2007","unstructured":"Viola, E., Wigderson, A.: Norms, xor lemmas, and lower bounds for GF(2) polynomials and multiparty protocols. In: CCC. IEEE, Los Alamitos (2007); Theory of Computing (to appear)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:24:19Z","timestamp":1606166659000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540853626","9783540853633"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}