{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T05:10:02Z","timestamp":1746335402980,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":59,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662445211"},{"type":"electronic","value":"9783662445228"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44522-8_3","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:12:23Z","timestamp":1407838343000},"page":"24-43","source":"Crossref","is-referenced-by-count":8,"title":["Communication Complexity Theory: Thirty-Five Years of Set Disjointness"],"prefix":"10.1007","author":[{"given":"Alexander A.","family":"Sherstov","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"3_CR1","doi-asserted-by":"publisher","first-page":"47","DOI":"10.4086\/toc.2005.v001a004","volume":"1","author":"S. Aaronson","year":"2005","unstructured":"Aaronson, S., Ambainis, A.: Quantum search of spatial regions. Theory of Computing\u00a01(1), 47\u201379 (2005)","journal-title":"Theory of Computing"},{"doi-asserted-by":"crossref","unstructured":"Aho, A.V., Ullman, J.D., Yannakakis, M.: On notions of information transfer in VLSI circuits. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC), pp. 133\u2013139 (1983)","key":"3_CR2","DOI":"10.1145\/800061.808742"},{"doi-asserted-by":"crossref","unstructured":"Alon, N., Frankl, P., R\u00f6dl, V.: Geometrical realization of set systems and probabilistic communication complexity. In: Proceedings of the Twenty-Sixth Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 277\u2013280 (1985)","key":"3_CR3","DOI":"10.1109\/SFCS.1985.30"},{"issue":"1","key":"3_CR4","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci.\u00a058(1), 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Babai, L., Frankl, P., Simon, J.: Complexity classes in communication complexity theory. In: Proceedings of the Twenty-Seventh Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 337\u2013347 (1986)","key":"3_CR5","DOI":"10.1109\/SFCS.1986.15"},{"issue":"2","key":"3_CR6","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."},{"issue":"4","key":"3_CR7","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","volume":"68","author":"Z. Bar-Yossef","year":"2004","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci.\u00a068(4), 702\u2013732 (2004)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Beame, P., Huynh-Ngoc, D.T.: Multiparty communication complexity and threshold circuit complexity of AC0. In: Proceedings of the Fiftieth Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 53\u201362 (2009)","key":"3_CR8","DOI":"10.1109\/FOCS.2009.12"},{"issue":"4","key":"3_CR9","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s00037-007-0220-2","volume":"15","author":"P. Beame","year":"2006","unstructured":"Beame, P., Pitassi, T., Segerlind, N., Wigderson, A.: A strong direct product theorem for corruption and the multiparty communication complexity of disjointness. Computational Complexity\u00a015(4), 391\u2013432 (2006)","journal-title":"Computational Complexity"},{"doi-asserted-by":"crossref","unstructured":"Ben-Aroya, A., Regev, O., de Wolf, R.: A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs. In: Proceedings of the Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 477\u2013486 (2008)","key":"3_CR10","DOI":"10.1109\/FOCS.2008.45"},{"key":"3_CR11","first-page":"441","volume":"3","author":"S. Ben-David","year":"2003","unstructured":"Ben-David, S., Eiron, N., Simon, H.U.: Limitations of learning via embeddings in Euclidean half spaces. J. Mach. Learn. Res.\u00a03, 441\u2013461 (2003)","journal-title":"J. Mach. Learn. Res."},{"doi-asserted-by":"crossref","unstructured":"Braverman, M., Ellen, F., Oshman, R., Pitassi, T., Vaikuntanathan, V.: A tight bound for set disjointness in the message-passing model. In: Proceedings of the Fifty-Fourth Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 668\u2013677 (2013)","key":"3_CR12","DOI":"10.1109\/FOCS.2013.77"},{"doi-asserted-by":"crossref","unstructured":"Braverman, M., Garg, A., Pankratov, D., Weinstein, O.: From information to exact communication. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC, pp. 151\u2013160 (2013)","key":"3_CR13","DOI":"10.1145\/2488608.2488628"},{"doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs.\u00a0classical communication and computation. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC, pp. 63\u201368 (1998)","key":"3_CR14","DOI":"10.1145\/276698.276713"},{"doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Khot, S., Sun, X.: Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In: Proceedings of the Eighteenth Annual IEEE Conference on Computational Complexity, CCC, pp. 107\u2013117 (2003)","key":"3_CR15","DOI":"10.1109\/CCC.2003.1214414"},{"doi-asserted-by":"crossref","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, pp. 94\u201399 (1983)","key":"3_CR16","DOI":"10.1145\/800061.808737"},{"unstructured":"Chattopadhyay, A.: Circuits, Communication, and Polynomials. Ph.D. thesis, McGill University (2008)","key":"3_CR17"},{"unstructured":"Chattopadhyay, A., Ada, A.: Multiparty communication complexity of disjointness. In: Electronic Colloquium on Computational Complexity (ECCC), report TR08-002 (January 2008)","key":"3_CR18"},{"issue":"4","key":"3_CR19","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1016\/S0022-0000(02)00019-3","volume":"65","author":"J. Forster","year":"2002","unstructured":"Forster, J.: A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. Syst. Sci.\u00a065(4), 612\u2013625 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/3-540-45294-X_15","volume-title":"FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science","author":"J. Forster","year":"2001","unstructured":"Forster, J., Krause, M., Lokam, S.V., Mubarakzjanov, R., Schmitt, N., Simon, H.U.: Relations between communication complexity, linear arrangements, and computational complexity. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) FSTTCS 2001. LNCS, vol.\u00a02245, pp. 171\u2013182. Springer, Heidelberg (2001)"},{"issue":"10","key":"3_CR21","doi-asserted-by":"publisher","first-page":"227","DOI":"10.4086\/toc.2010.v006a010","volume":"6","author":"D. Gavinsky","year":"2010","unstructured":"Gavinsky, D., Sherstov, A.A.: A separation of NP and coNP in multiparty communication complexity. Theory of Computing\u00a06(10), 227\u2013245 (2010)","journal-title":"Theory of Computing"},{"issue":"1","key":"3_CR22","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 in nearly optimal. Inf. Comput.\u00a0112(1), 51\u201354 (1994)","journal-title":"Inf. Comput."},{"doi-asserted-by":"crossref","unstructured":"Jain, R., Klauck, H., Nayak, A.: Direct product theorems for classical communication complexity via subdistribution bounds. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC, pp. 599\u2013608 (2008)","key":"3_CR23","DOI":"10.1145\/1374376.1374462"},{"issue":"4","key":"3_CR24","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B. Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math.\u00a05(4), 545\u2013557 (1992)","journal-title":"SIAM J. Discrete Math."},{"doi-asserted-by":"crossref","unstructured":"Klauck, H.: Rectangle size bounds and threshold covers in communication complexity. In: Proceedings of the Eighteenth Annual IEEE Conference on Computational Complexity, CCC, pp. 118\u2013134 (2003)","key":"3_CR25","DOI":"10.1109\/CCC.2003.1214415"},{"doi-asserted-by":"crossref","unstructured":"Klauck, H.: A strong direct product theorem for disjointness. In: Proceedings of the Forty-Second Annual ACM Symposium on Theory of Computing, STOC, pp. 77\u201386 (2010)","key":"3_CR26","DOI":"10.1145\/1806689.1806702"},{"issue":"5","key":"3_CR27","doi-asserted-by":"publisher","first-page":"1472","DOI":"10.1137\/05063235X","volume":"36","author":"H. Klauck","year":"2007","unstructured":"Klauck, H., \u0160palek, R., de Wolf, R.: Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM J. Comput.\u00a036(5), 1472\u20131493 (2007)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"3_CR28","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.jcss.2003.07.007","volume":"68","author":"A.R. Klivans","year":"2004","unstructured":"Klivans, A.R., Servedio, R.A.: Learning DNF in time $2^{\\tilde O(n^{1\/3})}$. J. Comput. Syst. Sci.\u00a068(2), 303\u2013318 (2004)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press (1997)","key":"3_CR29","DOI":"10.1017\/CBO9780511574948"},{"issue":"2","key":"3_CR30","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(2), 309\u2013336 (2009)","journal-title":"Computational Complexity"},{"issue":"4","key":"3_CR31","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s00493-007-2160-5","volume":"27","author":"N. Linial","year":"2007","unstructured":"Linial, N., Mendelson, S., Schechtman, G., Shraibman, A.: Complexity measures of sign matrices. Combinatorica\u00a027(4), 439\u2013463 (2007)","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Saks, M.E.: Lattices, M\u00f6bius functions and communication complexity. In: Proceedings of the Twenty-Ninth Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 81\u201390 (1988)","key":"3_CR32","DOI":"10.1109\/SFCS.1988.21924"},{"doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Schmidt, E.M.: Las Vegas is better than determinism in VLSI and distributed computing. In: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC, pp. 330\u2013337 (1982)","key":"3_CR33","DOI":"10.1145\/800070.802208"},{"issue":"2","key":"3_CR34","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I. Newman","year":"1991","unstructured":"Newman, I.: Private vs.\u00a0common random bits in communication complexity. Inf. Process. Lett.\u00a039(2), 67\u201371 (1991)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"3_CR35","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1016\/j.jet.2004.10.007","volume":"129","author":"N. Nisan","year":"2006","unstructured":"Nisan, N., Segal, I.: The communication requirements of efficient allocations and supporting prices. J. Economic Theory\u00a0129(1), 192\u2013224 (2006)","journal-title":"J. Economic Theory"},{"key":"3_CR36","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":"4","key":"3_CR37","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/BF01192527","volume":"15","author":"N. Nisan","year":"1995","unstructured":"Nisan, N., Wigderson, A.: On rank vs. communication complexity. Combinatorica\u00a015(4), 557\u2013565 (1995)","journal-title":"Combinatorica"},{"issue":"1","key":"3_CR38","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/0022-0000(86)90046-2","volume":"33","author":"R. Paturi","year":"1986","unstructured":"Paturi, R., Simon, J.: Probabilistic communication complexity. J. Comput. Syst. Sci.\u00a033(1), 106\u2013123 (1986)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"3_CR39","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02122698","volume":"10","author":"A.A. Razborov","year":"1990","unstructured":"Razborov, A.A.: Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica\u00a010(1), 81\u201393 (1990)","journal-title":"Combinatorica"},{"issue":"2","key":"3_CR40","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"A.A. Razborov","year":"1992","unstructured":"Razborov, A.A.: On the distributional complexity of disjointness. Theor. Comput. Sci.\u00a0106(2), 385\u2013390 (1992)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"3_CR41","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1070\/IM2003v067n01ABEH000422","volume":"67","author":"A.A. Razborov","year":"2003","unstructured":"Razborov, A.A.: Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics\u00a067(1), 145\u2013159 (2003)","journal-title":"Izvestiya: Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Razborov, A.A., Sherstov, A.A.: The sign-rank of AC0. SIAM J. Comput.\u00a039(5), 1833-1855 (2010)","key":"#cr-split#-3_CR42.1","DOI":"10.1137\/080744037"},{"unstructured":"preliminary version in Proceedings of the Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science, FOCS (2008)","key":"#cr-split#-3_CR42.2"},{"doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: Halfspace matrices. Computational Complexity\u00a017(2), 149-178 (2008)","key":"#cr-split#-3_CR43.1","DOI":"10.1007\/s00037-008-0242-4"},{"unstructured":"preliminary version in Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, CCC (2007)","key":"#cr-split#-3_CR43.2"},{"doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: Separating AC0 from depth-2 majority circuits. SIAM J. Comput.\u00a038(6), 2113-2129 (2009)","key":"#cr-split#-3_CR44.1","DOI":"10.1137\/08071421X"},{"unstructured":"preliminary version in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC (2007)","key":"#cr-split#-3_CR44.2"},{"doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: The pattern matrix method. SIAM J. Comput.\u00a040(6), 1969-2000 (2011)","key":"#cr-split#-3_CR45.1","DOI":"10.1137\/080733644"},{"unstructured":"preliminary version in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC) (2008)","key":"#cr-split#-3_CR45.2"},{"doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: The unbounded-error communication complexity of symmetric functions. Combinatorica\u00a031(5), 583-614 (2011)","key":"#cr-split#-3_CR46.1","DOI":"10.1007\/s00493-011-2580-0"},{"unstructured":"preliminary version in Proceedings of the Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science, FOCS (2008)","key":"#cr-split#-3_CR46.2"},{"doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: The multiparty communication complexity of set disjointness. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC, pp. 525\u2013544 (2012)","key":"3_CR47","DOI":"10.1145\/2213977.2214026"},{"doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: Strong direct product theorems for quantum communication and query complexity. SIAM J. Comput.\u00a041(5), 1122-1165 (2012)","key":"#cr-split#-3_CR48.1","DOI":"10.1137\/110842661"},{"unstructured":"preliminary version in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC (2011)","key":"#cr-split#-3_CR48.2"},{"doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: Communication lower bounds using directional derivatives. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC, pp. 921\u2013930 (2013)","key":"3_CR49","DOI":"10.1145\/2488608.2488725"},{"issue":"5-6","key":"3_CR50","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 & Computation\u00a09(5-6), 444\u2013460 (2009)","journal-title":"Quantum Information & Computation"},{"unstructured":"Tesson, P.: Computational complexity questions related to finite monoids and semigroups. Ph.D. thesis, McGill University (2003)","key":"3_CR51"},{"doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Some complexity questions related to distributive computing. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC, pp. 209\u2013213 (1979)","key":"3_CR52","DOI":"10.1145\/800135.804414"},{"doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Lower bounds by probabilistic arguments. In: Proceedings of the Twenty-Fourth Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 420\u2013428 (1983)","key":"3_CR53","DOI":"10.1109\/SFCS.1983.30"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44522-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:29:31Z","timestamp":1746332971000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-44522-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662445211","9783662445228"],"references-count":59,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44522-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}