{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:03:36Z","timestamp":1746331416096,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_76","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"919-930","source":"Crossref","is-referenced-by-count":6,"title":["An Improved Interactive Streaming Algorithm for the Distinct Elements Problem"],"prefix":"10.1007","author":[{"given":"Hartmut","family":"Klauck","sequence":"first","affiliation":[]},{"given":"Ved","family":"Prakash","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"76_CR1","doi-asserted-by":"crossref","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); Earlier version in STOC 1996","DOI":"10.1006\/jcss.1997.1545"},{"key":"76_CR2","unstructured":"Arora, S., Barak, B.: Complexity Theory: A Modern Approach. Cambridge University Press (2009)"},{"key":"76_CR3","doi-asserted-by":"crossref","unstructured":"Babai, L., Frankl, P., Simon, J.: Complexity classes in communication complexity theory. In: Proceedings of 27th IEEE FOCS, pp. 337\u2013347 (1986)","DOI":"10.1109\/SFCS.1986.15"},{"key":"76_CR4","unstructured":"Bach, E., Shallit, J.: Algorithmic number theory, volume 1: efficient algorithms. MIT Press, Cambridge (1996), http:\/\/www.math.uwaterloo.ca\/~shallit\/ant.html"},{"key":"76_CR5","first-page":"22","volume":"19","author":"A. Chakrabarti","year":"2012","unstructured":"Chakrabarti, A., Cormode, G., McGregor, A., Thaler, J.: Annotations in data streams. Electronic Colloquium on Computational Complexity (ECCC)\u00a019, 22 (2012)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"76_CR6","unstructured":"Chakrabarti, A., Cormode, G., McGregor, A., Thaler, J., Venkatasubramanian, S.: On interactivity in Arthur-Merlin communication and stream computation"},{"key":"76_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-642-15775-2_20","volume-title":"Algorithms \u2013 ESA 2010","author":"G. Cormode","year":"2010","unstructured":"Cormode, G., Mitzenmacher, M., Thaler, J.: Streaming Graph Computations with a Helpful Advisor. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol.\u00a06346, pp. 231\u2013242. Springer, Heidelberg (2010)"},{"key":"76_CR8","first-page":"90","volume-title":"Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 2012","author":"G. Cormode","year":"2012","unstructured":"Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 2012, pp. 90\u2013112. ACM, New York (2012)"},{"issue":"1","key":"76_CR9","doi-asserted-by":"crossref","first-page":"25","DOI":"10.14778\/2047485.2047488","volume":"5","author":"G. Cormode","year":"2011","unstructured":"Cormode, G., Thaler, J., Yi, K.: Verifying computations with streaming interactive proofs. Proc. VLDB Endow.\u00a05(1), 25\u201336 (2011)","journal-title":"Proc. VLDB Endow."},{"key":"76_CR10","unstructured":"Foley, J.: As big data explodes, are you ready for yottabytes? (June 2013), http:\/\/www.forbes.com\/sites\/oracle\/2013\/06\/21\/as-big-data-explodes-are-you-ready-for-yottabytes\/"},{"key":"76_CR11","first-page":"113","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008","author":"S. Goldwasser","year":"2008","unstructured":"Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 113\u2013122. ACM, New York (2008)"},{"key":"76_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1007\/978-3-642-39206-1_45","volume-title":"Automata, Languages, and Programming","author":"T. Gur","year":"2013","unstructured":"Gur, T., Raz, R.: Arthur-Merlin Streaming Complexity. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 528\u2013539. Springer, Heidelberg (2013)"},{"key":"76_CR13","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1109\/TIT.1972.1054893","volume":"18","author":"J. Justesen","year":"1972","unstructured":"Justesen, J.: A class of constructive asymptotically good algebraic codes. IEEE Transactions on Information Theory\u00a018, 652\u2013656 (1972)","journal-title":"IEEE Transactions on Information Theory"},{"key":"76_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1807085.1807094","volume-title":"Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010","author":"D.M. Kane","year":"2010","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.P.: An optimal algorithm for the distinct elements problem. In: Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010, pp. 41\u201352. ACM, New York (2010)"},{"key":"76_CR15","doi-asserted-by":"crossref","unstructured":"Klauck, H.: Rectangle size bounds and threshold covers in communication complexity. In: IEEE Conference on Computational Complexity, pp. 118\u2013134. IEEE Computer Society (2003)","DOI":"10.1109\/CCC.2003.1214415"},{"key":"76_CR16","doi-asserted-by":"crossref","unstructured":"Klauck, H.: On Arthur Merlin games in communication complexity. CoRR, abs\/1101.0523 (2011)","DOI":"10.1109\/CCC.2011.33"},{"key":"76_CR17","first-page":"305","volume-title":"Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS 2013","author":"H. Klauck","year":"2013","unstructured":"Klauck, H., Prakash, V.: Streaming computations with a loquacious prover. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS 2013, pp. 305\u2013320. ACM, New York (2013)"},{"key":"76_CR18","unstructured":"Klauck, H., Prakash, V.: An improved interactive streaming algorithm for the distinct elements problem (2014), Paper available at http:\/\/arxiv.org\/abs\/1402.6800"},{"issue":"1","key":"76_CR19","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/s00037-008-0239-z","volume":"17","author":"O. Lachish","year":"2008","unstructured":"Lachish, O., Newman, I., Shapira, A.: Space complexity vs. query complexity. Computational Complexity\u00a017(1), 70\u201393 (2008)","journal-title":"Computational Complexity"},{"issue":"4","key":"76_CR20","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. J. ACM\u00a039(4), 859\u2013868 (1992)","journal-title":"J. ACM"},{"key":"76_CR21","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.: Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science\u00a01(2) (2005)","DOI":"10.1561\/0400000002"},{"issue":"4","key":"76_CR22","first-page":"333","volume":"41","author":"A. Razborov","year":"1987","unstructured":"Razborov, A.: Lower bounds on the size of bounded-depth networks over a complete basis with logical addition (russian). Matematicheskie Zametki\u00a041(4), 333\u2013338 (1987)","journal-title":"Matematicheskie Zametki"},{"issue":"2","key":"76_CR23","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"A. Razborov","year":"1992","unstructured":"Razborov, A.: On the distributional complexity of disjointness. Theoretical Computer Science\u00a0106(2), 385\u2013390 (1992)","journal-title":"Theoretical Computer Science"},{"key":"76_CR24","unstructured":"Razborov, A.A., Epstein, M.A.: Lower bounds for the size of circuits of bounded depth in basis (1986)"},{"key":"76_CR25","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for boolean circuit complexity. In: Proceedings of 19th ACM STOC, pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"},{"key":"76_CR26","doi-asserted-by":"crossref","unstructured":"van Lint, J.H.: Introduction to Coding Theory (Graduate Texts in Mathematics. 3rd rev. and exp. edn. Springer (1998)","DOI":"10.1007\/978-3-642-58575-3"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_76","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:31:03Z","timestamp":1746264663000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_76"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_76","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}