{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T15:39:26Z","timestamp":1774625966717,"version":"3.50.1"},"reference-count":72,"publisher":"Elsevier","isbn-type":[{"value":"9780120121441","type":"print"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1016\/s0065-2458(08)60342-3","type":"book-chapter","created":{"date-parts":[[2011,1,19]],"date-time":"2011-01-19T05:56:15Z","timestamp":1295416575000},"page":"331-360","source":"Crossref","is-referenced-by-count":253,"title":["Communication Complexity"],"prefix":"10.1016","author":[{"given":"Eyal","family":"Kushilevitz","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0065-2458(08)60342-3_bb0005","first-page":"133","article-title":"On notions of information transfer in VLSI circuits","author":"Aho","year":"1983"},{"issue":"2","key":"10.1016\/S0065-2458(08)60342-3_rf0010","first-page":"118","article-title":"Meanders and their applications in lower bound arguments","volume":"37","author":"Alon","year":"1988","journal-title":"JCSS"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0015","first-page":"410","author":"Early version","year":"1986"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0015","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1002\/jgt.3190130413","article-title":"A counterexample to the rank-coloring conjecture","volume":"13","author":"Alon","year":"1989","journal-title":"J. of Graph Theory"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0020","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0304-3975(90)90080-2","article-title":"Lower bounds to the complexity of symmetric Boolean functions","volume":"74","author":"Babai","year":"1990","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"10.1016\/S0065-2458(08)60342-3_rf0030","first-page":"204","article-title":"Multiparty protocols, pseudorandom generators for LOGSPACE, and time\u2013space trade-off","volume":"45","author":"Babai","year":"1992","journal-title":"JCSS"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0035","first-page":"1","author":"Early version","year":"1989"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0030","first-page":"361","article-title":"Simultaneous messages vs. communication","author":"Babai","year":"1995"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0035","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","article-title":"Graph-based Algorithms for Boolean function manipulations","volume":"35","author":"Bryant","year":"1986","journal-title":"IEEE Transactions on Computers"},{"issue":"2","key":"10.1016\/S0065-2458(08)60342-3_bb0040","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1145\/136035.136043","article-title":"Symbolic Boolean manipulation with ordered binary decision diagrams","volume":"24","author":"Bryant","year":"1992","journal-title":"ACM Computing Surveys"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0045","first-page":"94","article-title":"Multiparty protocols","author":"Chandra","year":"1983"},{"issue":"2","key":"10.1016\/S0065-2458(08)60342-3_rf0060","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1137\/0217015","article-title":"Unbiased bits from sources of weak randomness and probabilistic communication complexit","volume":"17","author":"Chor","year":"1988","journal-title":"SIAM J. Computing"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0065","first-page":"429","author":"Early version","year":"1985"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0055","series-title":"The recognition problem for the set of perfect squares","author":"Cobham","year":"1966"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0075","first-page":"326","article-title":"A comparison of two lower bound methods for communication complexity","author":"Dietzfelbinger","year":"1994"},{"issue":"1","key":"10.1016\/S0065-2458(08)60342-3_rf0080","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(87)90037-X","article-title":"Lower bounds on communication complexity","volume":"73","author":"\u010euri\u0161","year":"1987","journal-title":"Information and Computation"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0085","first-page":"81","author":"Early version","year":"1984"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0070","first-page":"249","article-title":"Communication complexity towards lower bounds on circuit depth","author":"Edmonds","year":"1991"},{"issue":"4","key":"10.1016\/S0065-2458(08)60342-3_rf0095","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1137\/S0097539792235864","article-title":"Amortized communication complexity","volume":"24","author":"Feder","year":"1995","journal-title":"SIAM J. Computing"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0100","first-page":"239","author":"Early version","year":"1991"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0080","first-page":"178","article-title":"The power of randomness for communication complexity","author":"F\u00fcrer","year":"1987"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0085","first-page":"85","article-title":"Communication complexity and lower bounds for threshold circuits. Chapter 3 in","author":"Goldmann","year":"1994"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0115","first-page":"433","article-title":"Monotone separation of logarithmic space from logarithmic depth","volume":"50","author":"Gringi","year":"1995","journal-title":"JCSS"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0120","first-page":"294","author":"Early version","year":"1991"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0095","first-page":"707","article-title":"On linear decision trees computing Boolean functions","author":"Groger","year":"1991"},{"issue":"1","key":"10.1016\/S0065-2458(08)60342-3_bb0100","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1006\/inco.1994.1051","article-title":"The BNS lower bound for multiparty protocols is nearly optimal","volume":"112","author":"Grolmusz","year":"1994","journal-title":"Information and Computation"},{"issue":"5","key":"10.1016\/S0065-2458(08)60342-3_rf0135","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1137\/0222057","article-title":"Different modes of communication","volume":"22","author":"Halstenberg","year":"1993","journal-title":"SIAM J. Computing"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0140","first-page":"162","author":"Early version","year":"1988"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0110","first-page":"610","article-title":"On the power of small-depth threshold circuits","author":"H\u00e5stad","year":"1990"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0115","series-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","year":"1979"},{"issue":"4","key":"10.1016\/S0065-2458(08)60342-3_rf0155","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/0405044","article-title":"The probabilistic communication complexity of set intersection","volume":"5","author":"Kalyanasundaram","year":"1992","journal-title":"SIAM J. Discrete Math"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0160","first-page":"41","author":"Early version","year":"1987"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0125","series-title":"Communication Complexity: A New Approach to Circuit Depth","author":"Karchmer","year":"1989"},{"issue":"2","key":"10.1016\/S0065-2458(08)60342-3_rf0170","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/0403021","article-title":"Monotone circuits for connectivity require superlogarithmic depth","volume":"3","author":"Karchmer","year":"1990","journal-title":"SIAM J. Discrete Math"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0175","first-page":"539","author":"Early version","year":"1988"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0135","first-page":"299","article-title":"On proving super-logarithmic depth lower bounds via the direct sum in communication complexity","author":"Karchmer","year":"1991"},{"issue":"1","key":"10.1016\/S0065-2458(08)60342-3_rf0185","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1137\/S0895480192238482","article-title":"Fractional covers and communication complexity","volume":"8","author":"Karchmer","year":"1995","journal-title":"SIAMJ. Discrete Math"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0190","first-page":"262","author":"Early version","year":"1992"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0145","series-title":"Communication Complexity","author":"Kushilevitz","year":"1996"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0150","doi-asserted-by":"crossref","DOI":"10.1145\/237814.237817","article-title":"The linear-array conjecture of communication complexity is false","author":"Kushilevitz","year":"1996"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0155","series-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes","author":"Leighton","year":"1991"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0160","first-page":"835","article-title":"VLSI Theory","author":"Lengauer","year":"1990"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0215","first-page":"300","article-title":"Lower bounds for VLSI","author":"Lipton","year":"1981"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0170","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","article-title":"Applications of a planar separator theorem","volume":"9","author":"Lipton","year":"1980","journal-title":"SIAM J. Computing"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0175","series-title":"Paths, Flows, and VLSI Layout","article-title":"Communication complexity: A Survey","author":"Lov\u00e1sz","year":"1990"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0180","first-page":"330","article-title":"Las-Vegas is better than determinism in VLSI and distributed computing","author":"Mehlhorn","year":"1982"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0185","first-page":"625","article-title":"Lower bounds for union-split-find related problems on random access machines","author":"Miltersen","year":"1994"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0190","first-page":"103","article-title":"On data structures and asymmetric communication complexity","author":"Miltersen","year":"1995"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0195","series-title":"Threshold Logic and Its Applications","author":"Muroga","year":"1971"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0200","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","article-title":"Private vs. common random bits in communication complexity","volume":"39","author":"Newman","year":"1991","journal-title":"Information Processing Letters"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0205","first-page":"301","article-title":"The communication complexity of threshold gates","volume":"Vol. 1","author":"Nisan","year":"1993"},{"issue":"1","key":"10.1016\/S0065-2458(08)60342-3_rf0260","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1137\/0222016","article-title":"Rounds in communication complexity revisited","volume":"22","author":"Nisan","year":"1993","journal-title":"SIAM J. Computing"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0265","first-page":"419","author":"Early version","year":"1991"},{"issue":"4","key":"10.1016\/S0065-2458(08)60342-3_rf0270","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1007\/BF01192527","article-title":"On rank vs. communication complexity","volume":"15","author":"Nisan","year":"1995","journal-title":"Combinatorica"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0275","first-page":"831","author":"Early version","year":"1994"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0220","series-title":"Complexity in Information Theory","first-page":"16","article-title":"Communication complexity","author":"Orlitsky","year":"1988"},{"issue":"2","key":"10.1016\/S0065-2458(08)60342-3_rf0285","first-page":"260","article-title":"Communication complexity","volume":"28","author":"Papadimitriou","year":"1984","journal-title":"JCSS"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0290","first-page":"196","author":"Early version","year":"1982"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0230","first-page":"523","article-title":"Modified ranks of tensors and the size of circuits","author":"Pudl\u00e1k","year":"1993"},{"issue":"4","key":"10.1016\/S0065-2458(08)60342-3_rf0300","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1007\/BF01192528","article-title":"On the \u201clog rank\u201d conjecture in communication complexity","volume":"15","author":"Raz","year":"1995","journal-title":"Combinatorica"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0305","first-page":"168","author":"Early version","year":"1993"},{"issue":"3","key":"10.1016\/S0065-2458(08)60342-3_rf0310","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1145\/146637.146684","article-title":"Monotone circuits for matching require linear depth","volume":"39","author":"Raz","year":"1992","journal-title":"JACM"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0315","first-page":"287","author":"Early version","year":"1990"},{"issue":"1","key":"10.1016\/S0065-2458(08)60342-3_bb0245","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02122698","article-title":"Applications of matrix methods to the theory of lower bounds in computational complexity","volume":"10","author":"Razborov","year":"1990","journal-title":"Combinatorica"},{"issue":"2","key":"10.1016\/S0065-2458(08)60342-3_rf0325","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","article-title":"On the distributional complexity of disjointness","volume":"106","author":"Razborov","year":"1992","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S0065-2458(08)60342-3_rf0330","first-page":"249","author":"Early version","year":"1990"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0255","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/0012-365X(92)90691-8","article-title":"The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear","volume":"108","author":"Razborov","year":"1992","journal-title":"Discrete Math"},{"issue":"2","key":"10.1016\/S0065-2458(08)60342-3_bb0260","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1109\/18.312169","article-title":"Lower bounds on threshold and related circuits via communication complexity","volume":"40","author":"Roychowdhury","year":"1994","journal-title":"IEEE Transactions on Information Theory."},{"issue":"379\u2013423","key":"10.1016\/S0065-2458(08)60342-3_bb0265","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1002\/j.1538-7305.1948.tb00917.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell System Techn. Jour."},{"key":"10.1016\/S0065-2458(08)60342-3_bb0270","series-title":"Discrete Neural Computation\u2014A Theoretical Foundation","author":"Siu","year":"1995"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0275","first-page":"81","article-title":"Area-time complexity for VLSI","author":"Thompson","year":"1979"},{"key":"10.1016\/S0065-2458(08)60342-3_bb0280","first-page":"209","article-title":"Some complexity questions related to distributed computing","author":"Yao","year":"1979"}],"container-title":["Advances in Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0065245808603423?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0065245808603423?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T23:51:09Z","timestamp":1559951469000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0065245808603423"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9780120121441"],"references-count":72,"URL":"https:\/\/doi.org\/10.1016\/s0065-2458(08)60342-3","relation":{},"ISSN":["0065-2458"],"issn-type":[{"value":"0065-2458","type":"print"}],"subject":[],"published":{"date-parts":[[1997]]}}}