{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:37Z","timestamp":1778807857584,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642036842","type":"print"},{"value":"9783642036859","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-03685-9_42","type":"book-chapter","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T02:39:51Z","timestamp":1250822391000},"page":"562-573","source":"Crossref","is-referenced-by-count":27,"title":["Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND"],"prefix":"10.1007","author":[{"given":"T. S.","family":"Jayram","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"42_CR1","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0304-3975(95)00157-3","volume":"157","author":"F. Ablayev","year":"1996","unstructured":"Ablayev, F.: Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theoretical Computer Science\u00a0157(2), 139\u2013159 (1996)","journal-title":"Theoretical Computer Science"},{"key":"42_CR2","unstructured":"Andoni, A., Jayram, T.S., Patrascu, M.: Non-embeddability and sketching complexity via information geometry (2009)"},{"issue":"1","key":"42_CR3","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. Journal of Computer and System Sciences\u00a058(1), 137\u2013147 (1999)","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"42_CR4","doi-asserted-by":"publisher","first-page":"1930","DOI":"10.1109\/18.265501","volume":"39","author":"R. Bar-Yehuda","year":"1993","unstructured":"Bar-Yehuda, R., Chor, B., Kushilevitz, E., Orlitsky, A.: Privacy, additional information, and communication. IEEE Transactions on Information Theory\u00a039(6), 1930\u20131943 (1993)","journal-title":"IEEE Transactions on Information Theory"},{"key":"42_CR5","doi-asserted-by":"publisher","first-page":"708","DOI":"10.1145\/1109557.1109634","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006","author":"L. Bhuvanagiri","year":"2006","unstructured":"Bhuvanagiri, L., Ganguly, S., Kesh, D., Saha, C.: Simpler algorithm for estimating frequency moments of data streams. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pp. 708\u2013713. ACM Press, New York (2006)"},{"key":"42_CR6","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45726-7_1","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"Z. Bar-Yossef","year":"2002","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D., Trevisan, L.: Counting distinct elements in a data stream. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 1\u201310. Springer, Heidelberg (2002)"},{"issue":"4","key":"42_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."},{"issue":"1","key":"42_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(03)00400-6","volume":"312","author":"M. Charikar","year":"2004","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. Theor. Comput. Sci.\u00a0312(1), 3\u201315 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Khot, S., Sun, X.: Near-optimal lower bounds on the multiparty communication complexity of set-disjointness. In: Proceedings of the 18th Annual IEEE Conference on Computational Complexity, pp. 107\u2013117 (2003)","DOI":"10.1109\/CCC.2003.1214414"},{"key":"42_CR10","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: Proceedings of the 42nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 270\u2013278 (2001)","DOI":"10.1109\/SFCS.2001.959901"},{"key":"42_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of Cuts and Metrics","author":"M. Deza","year":"1997","unstructured":"Deza, M., Laurent, M.: Geometry of Cuts and Metrics. Springer, Heidelberg (1997)"},{"issue":"2","key":"42_CR12","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","volume":"31","author":"P. Flajolet","year":"1985","unstructured":"Flajolet, P., Martin, G.N.: Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci.\u00a031(2), 182\u2013209 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"42_CR13","unstructured":"Gronemeier, A.: Asymptotically optimal lower bounds on the nih-multi-party information complexity of the and-function and disjointness. In: Albers, S., Marion, J.-Y. (eds.) STACS, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany. Dagstuhl Seminar Proceedings, vol.\u00a009001, pp. 505\u2013516 (2009)"},{"issue":"3","key":"42_CR14","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1145\/1147954.1147955","volume":"53","author":"P. Indyk","year":"2006","unstructured":"Indyk, P.: Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM\u00a053(3), 307\u2013323 (2006)","journal-title":"J. ACM"},{"key":"42_CR15","doi-asserted-by":"crossref","unstructured":"Indyk, P., Woodruff, D.P.: Optimal approximations of the frequency moments of data streams. In: STOC, pp. 202\u2013208 (2005)","DOI":"10.1145\/1060590.1060621"},{"key":"42_CR16","doi-asserted-by":"crossref","unstructured":"Jayram, T.S., Woodruff, D.: The data stream space complexity of cascaded norms (submitted, 2009)","DOI":"10.1109\/FOCS.2009.82"},{"key":"42_CR17","unstructured":"Monemizadeh, M., Woodruff, D.: l p -sampling with applications (manuscript)"},{"key":"42_CR18","unstructured":"Sloane, N.: The on-line encyclopedia of integer sequences!, http:\/\/www.research.att.com\/~njas\/sequences\/A048651"},{"key":"42_CR19","doi-asserted-by":"crossref","unstructured":"Saks, M., Sun, X.: Space lower bounds for distance approximation in the data stream model. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp. 360\u2013369 (2002)","DOI":"10.1145\/509907.509963"},{"key":"42_CR20","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Some complexity questions related to distributive computing. In: Proceedings of the 11th ACM Symposium on Theory of Computing (STOC), pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"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-03685-9_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T20:24:15Z","timestamp":1739305455000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}