{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T03:40:10Z","timestamp":1743824410898,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325113"},{"type":"electronic","value":"9783642325120"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_44","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"517-528","source":"Crossref","is-referenced-by-count":10,"title":["Sparse and Lopsided Set Disjointness via Information Theory"],"prefix":"10.1007","author":[{"given":"Anirban","family":"Dasgupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Sivakumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"44_CR1","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0304-3975(95)00157-3","volume":"157","author":"F.M. Ablayev","year":"1996","unstructured":"Ablayev, F.M.: Lower bounds for one-way probabilistic communication complexity and their application to space complexity. TCS\u00a0157(2), 139\u2013159 (1996)","journal-title":"TCS"},{"key":"44_CR2","doi-asserted-by":"crossref","unstructured":"Babai, L., Frankl, P., Simon, J.: Complexity classes in communication complexity theory (preliminary version). In: FOCS, pp. 337\u2013347 (1986)","DOI":"10.1109\/SFCS.1986.15"},{"key":"44_CR3","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: Information theory methods in communication complexity. In: CCC, pp. 93\u2013102 (2002)","DOI":"10.1109\/CCC.2002.1004344"},{"issue":"4","key":"44_CR4","first-page":"702","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. JCSS\u00a068(4), 702\u2013732 (2004)","journal-title":"JCSS"},{"key":"44_CR5","doi-asserted-by":"crossref","unstructured":"Barak, B., Braverman, M., Chen, X., Rao, A.: How to compress interactive communication. In: STOC, pp. 67\u201376 (2010)","DOI":"10.1145\/1806689.1806701"},{"key":"44_CR6","doi-asserted-by":"crossref","unstructured":"Braverman, M., Rao, A.: Information equals amortized communication. In: FOCS, pp. 748\u2013757 (2011)","DOI":"10.1109\/FOCS.2011.86"},{"key":"44_CR7","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Shi, Y., Wirth, A., Yao, A.C.-C.: Informational complexity and the direct sum problem for simultaneous message complexity. In: FOCS, pp. 270\u2013278 (2001)","DOI":"10.1109\/SFCS.2001.959901"},{"key":"44_CR8","doi-asserted-by":"crossref","unstructured":"Cover, T.M., Thomas, J.A.: Elements of Information Theory. John Wiley & Sons, Inc. (1991)","DOI":"10.1002\/0471200611"},{"issue":"1","key":"44_CR9","first-page":"438","volume":"56","author":"P. Harsha","year":"2010","unstructured":"Harsha, P., Jain, R., McAllester, D.A., Radhakrishnan, J.: The communication complexity of correlation. TOIT\u00a056(1), 438\u2013449 (2010)","journal-title":"TOIT"},{"issue":"1","key":"44_CR10","doi-asserted-by":"publisher","first-page":"211","DOI":"10.4086\/toc.2007.v003a011","volume":"3","author":"J. H\u00e5stad","year":"2007","unstructured":"H\u00e5stad, J., Wigderson, A.: The randomized communication complexity of set disjointness. ToC\u00a03(1), 211\u2013219 (2007)","journal-title":"ToC"},{"key":"44_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/3-540-45061-0_26","volume-title":"Automata, Languages and Programming","author":"R. Jain","year":"2003","unstructured":"Jain, R., Radhakrishnan, J., Sen, P.: A Direct Sum Theorem in Communication Complexity Via Message Compression. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 300\u2013315. Springer, Heidelberg (2003)"},{"key":"44_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1007\/978-3-642-03685-9_42","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"T.S. Jayram","year":"2009","unstructured":"Jayram, T.S.: Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 562\u2013573. Springer, Heidelberg (2009)"},{"key":"44_CR13","doi-asserted-by":"crossref","unstructured":"Jayram, T.S., Kopparty, S., Raghavendra, P.: On the communication complexity of read-once AC0 formulae. In: CCC, pp. 329\u2013340 (2009)","DOI":"10.1109\/CCC.2009.39"},{"key":"44_CR14","doi-asserted-by":"crossref","unstructured":"Jayram, T.S., Kumar, R., Sivakumar, D.: Two applications of information complexity. In: STOC, pp. 673\u2013682 (2003)","DOI":"10.1145\/780542.780640"},{"issue":"4","key":"44_CR15","doi-asserted-by":"crossref","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. SIDMA\u00a05(4), 545\u2013557 (1992)","journal-title":"SIDMA"},{"issue":"1","key":"44_CR16","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s000370050018","volume":"8","author":"I. Kremer","year":"1999","unstructured":"Kremer, I., Nisan, N., Ron, D.: On randomized one-round communication complexity. Computational Complexity\u00a08(1), 21\u201349 (1999)","journal-title":"Computational Complexity"},{"key":"44_CR17","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"issue":"3","key":"44_CR18","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1137\/09075336X","volume":"40","author":"M. P\u0103tra\u015fcu","year":"2011","unstructured":"P\u0103tra\u015fcu, M.: Unifying the landscape of cell-probe lower bounds. SICOMP\u00a040(3), 827\u2013847 (2011)","journal-title":"SICOMP"},{"issue":"3","key":"44_CR19","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SICOMP\u00a027(3), 763\u2013803 (1998)","journal-title":"SICOMP"},{"issue":"2","key":"44_CR20","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. TCS\u00a0106(2), 385\u2013390 (1992)","journal-title":"TCS"},{"key":"44_CR21","doi-asserted-by":"crossref","unstructured":"Saks, M.E., Sun, X.: Space lower bounds for distance approximation in the data stream model. In: STOC, pp. 360\u2013369 (2002)","DOI":"10.1145\/509907.509963"},{"issue":"3","key":"44_CR22","first-page":"364","volume":"74","author":"P. Sen","year":"2008","unstructured":"Sen, P., Venkatesh, S.: Lower bounds for predecessor searching in the cell probe model. JCSS\u00a074(3), 364\u2013385 (2008)","journal-title":"JCSS"}],"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-642-32512-0_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T03:24:59Z","timestamp":1743823499000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}