{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T19:55:07Z","timestamp":1725738907034},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_45","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T17:20:16Z","timestamp":1372785616000},"page":"528-539","source":"Crossref","is-referenced-by-count":9,"title":["Arthur-Merlin Streaming Complexity"],"prefix":"10.1007","author":[{"given":"Tom","family":"Gur","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"45_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1490270.1490272","volume":"1","author":"S. Aaronson","year":"2009","unstructured":"Aaronson, S., Wigderson, A.: Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory\u00a01, 2:1\u20132:54 (2009)","journal-title":"ACM Trans. Comput. Theory"},{"key":"45_CR2","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/237814.237823","volume-title":"Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC 1996","author":"N. Alon","year":"1996","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC 1996, pp. 20\u201329. ACM, New York (1996)"},{"doi-asserted-by":"crossref","unstructured":"Beyer, K.S., Haas, P.J., Reinwald, B., Sismanis, Y., Gemulla, R.: On synopses for distinct-value estimation under multiset operations. In: SIGMOD Conference, pp. 199\u2013210 (2007)","key":"45_CR3","DOI":"10.1145\/1247480.1247504"},{"doi-asserted-by":"crossref","unstructured":"Brody, J., Chakrabarti, A.: A multi-round communication lower bound for gap hamming and some consequences. In: IEEE Conference on Computational Complexity, pp. 358\u2013368 (2009)","key":"45_CR4","DOI":"10.1109\/CCC.2009.31"},{"key":"45_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-642-02927-1_20","volume-title":"Automata, Languages and Programming","author":"A. Chakrabarti","year":"2009","unstructured":"Chakrabarti, A., Cormode, G., Mcgregor, A.: Annotations in data streams. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 222\u2013234. Springer, Heidelberg (2009)"},{"key":"45_CR6","first-page":"51","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC 2011","author":"A. Chakrabarti","year":"2011","unstructured":"Chakrabarti, A., Regev, O.: An optimal lower bound on the communication complexity of gap-hamming-distance. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 51\u201360. ACM, New York (2011)"},{"key":"45_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/978-3-642-22792-9_9","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"K.-M. Chung","year":"2011","unstructured":"Chung, K.-M., Kalai, Y.T., Liu, F.-H., Raz, R.: Memory delegation. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.\u00a06841, pp. 151\u2013168. Springer, Heidelberg (2011)"},{"doi-asserted-by":"crossref","unstructured":"Cormode, G., Mitzenmacher, M., Thaler, J.: Streaming graph computations with a helpful advisor. CoRR, abs\/1004.2899 (2010)","key":"45_CR8","DOI":"10.1007\/978-3-642-15775-2_20"},{"doi-asserted-by":"crossref","unstructured":"Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. CoRR (May 2011)","key":"45_CR9","DOI":"10.1145\/2090236.2090245"},{"doi-asserted-by":"crossref","unstructured":"Flajolet, P., Martin, G.N.: Probabilistic counting. In: FOCS, pp. 76\u201382 (1983)","key":"45_CR10","DOI":"10.1109\/SFCS.1983.46"},{"doi-asserted-by":"crossref","unstructured":"Ganguly, S., Kanpur, I., Garofalakis, M.: Join-distinct aggregate estimation over update streams. In: Proc. ACM PODS (2005)","key":"45_CR11","DOI":"10.1145\/1065167.1065200"},{"doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: STOC, pp. 113\u2013122 (2008)","key":"45_CR12","DOI":"10.1145\/1374376.1374396"},{"key":"45_CR13","first-page":"20","volume":"20","author":"T. Gur","year":"2013","unstructured":"Gur, T., Raz, R.: Arthur-merlin streaming complexity. Electronic Colloquium on Computational Complexity (ECCC)\u00a020, 20 (2013)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"doi-asserted-by":"crossref","unstructured":"Indyk, P., Woodruff, D.P.: Tight lower bounds for the distinct elements problem. In: FOCS, pp. 283\u2013289 (2003)","key":"45_CR14","DOI":"10.1109\/SFCS.2003.1238202"},{"doi-asserted-by":"crossref","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.P.: An optimal algorithm for the distinct elements problem. In: PODS, pp. 41\u201352 (2010)","key":"45_CR15","DOI":"10.1145\/1807085.1807094"},{"doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Now Publishers (2005)","key":"45_CR16","DOI":"10.1561\/0400000002"},{"doi-asserted-by":"crossref","unstructured":"Raz, R., Shpilka, A.: On the power of quantum proofs. In: Annual IEEE Conference on Computational Complexity, pp. 260\u2013274 (2004)","key":"45_CR17","DOI":"10.1109\/CCC.2004.1313849"},{"issue":"4","key":"45_CR18","first-page":"333","volume":"41","author":"A. Razborov","year":"1987","unstructured":"Razborov, A.: Lower bounds for the size of circuits of bounded depth with basis {\u2009\u2227\u2009,\u2009\u2295\u2009}. Notes of the Academy of Science of the USSR\u00a041(4), 333\u2013338 (1987)","journal-title":"Notes of the Academy of Science of the USSR"},{"key":"45_CR19","first-page":"63","volume":"18","author":"A.A. Sherstov","year":"2011","unstructured":"Sherstov, A.A.: The communication complexity of gap hamming distance. Electronic Colloquium on Computational Complexity (ECCC)\u00a018, 63 (2011)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"45_CR20","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/28395.28404","volume-title":"Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC 1987","author":"R. Smolensky","year":"1987","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for boolean circuit complexity. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC 1987, pp. 77\u201382. ACM, New York (1987)"},{"key":"45_CR21","first-page":"51","volume":"18","author":"T. Vidick","year":"2011","unstructured":"Vidick, T.: A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the gap-hamming-distance problem. Electronic Colloquium on Computational Complexity (ECCC)\u00a018, 51 (2011)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"45_CR22","first-page":"420","volume-title":"Proceedings of the 24th Annual Symposium on Foundations of Computer Science","author":"A.C. Yao","year":"1983","unstructured":"Yao, A.C.: Lower bounds by probabilistic arguments. In: Proceedings of the 24th Annual Symposium on Foundations of Computer Science, pp. 420\u2013428. IEEE Computer Society, Washington, DC (1983)"}],"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-642-39206-1_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,2]],"date-time":"2023-07-02T20:55:39Z","timestamp":1688331339000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}