{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:46:24Z","timestamp":1781077584420,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1751040 (CAREER)"],"award-info":[{"award-number":["CCF-1751040 (CAREER)"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384278","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1223-1236","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Separations and equivalences between turnstile streaming and linear sketching"],"prefix":"10.1145","author":[{"given":"John","family":"Kallaugher","sequence":"first","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eric","family":"Price","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095156"},{"key":"e_1_3_2_1_2_1","volume-title":"LIPIcs-Leibniz International Proceedings in Informatics","volume":"50","author":"Ai Yuqing","year":"2016","unstructured":"[AHLW16] Yuqing Ai , Wei Hu , Yi Li , and David P Woodruf . New characterizations in turnstile streams with applications . In LIPIcs-Leibniz International Proceedings in Informatics , volume 50 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik , 2016 . [AHLW16] Yuqing Ai, Wei Hu, Yi Li, and David P Woodruf. New characterizations in turnstile streams with applications. In LIPIcs-Leibniz International Proceedings in Informatics, volume 50. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039799"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884528"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684566"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198388"},{"key":"e_1_3_2_1_8_1","volume-title":"An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55 ( 1 ): 58-75","author":"Cormode Graham","year":"2005","unstructured":"[CM05] Graham Cormode and Shan Muthukrishnan . An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55 ( 1 ): 58-75 , 2005 . [CM05] Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55 ( 1 ): 58-75, 2005."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195908002520"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060622"},{"key":"e_1_3_2_1_11_1","unstructured":"[Gan08] Sumit Ganguly. Lower bounds on frequency estimation of data streams.  [Gan08] Sumit Ganguly. Lower bounds on frequency estimation of data streams."},{"key":"e_1_3_2_1_12_1","first-page":"204","volume-title":"International Computer Science Symposium in Russia","author":"In","unstructured":"In International Computer Science Symposium in Russia , pages 204 - 215 . In International Computer Science Symposium in Russia, pages 204-215."},{"key":"e_1_3_2_1_13_1","unstructured":"Springer 2008.  Springer 2008."},{"key":"e_1_3_2_1_14_1","volume-title":"CCC","author":"Hosseini Kaave","year":"2019","unstructured":"[HLY19] Kaave Hosseini , Shachar Lovett , and Grigory Yaroslavtsev . Optimality of linear sketching under modular updates . CCC , 2019 . [HLY19] Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev. Optimality of linear sketching under modular updates. CCC, 2019."},{"key":"e_1_3_2_1_15_1","volume-title":"Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM (JACM), 53 ( 3 ): 307-323","author":"Indyk Piotr","year":"2006","unstructured":"[Ind06] Piotr Indyk . Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM (JACM), 53 ( 3 ): 307-323 , 2006 . [Ind06] Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM (JACM), 53 ( 3 ): 307-323, 2006."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993720"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11533719_72"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196986"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_3_2_1_20_1","first-page":"556","volume-title":"2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Kallaugher John","unstructured":"[KKP18] John Kallaugher , Michael Kapralov , and Eric Price . The sketching complexity of graph and hypergraph counting . In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages 556 - 567 . [KKP18] John Kallaugher, Michael Kapralov, and Eric Price. The sketching complexity of graph and hypergraph counting. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 556-567."},{"key":"e_1_3_2_1_21_1","unstructured":"IEEE 2018.  IEEE 2018."},{"key":"e_1_3_2_1_22_1","unstructured":"[KLM+14] Michael Kapralov Yin Tat Lee Cameron Musco Christopher Musco and Aaron Sidford. Single pass spectral sparsification in dynamic streams.  [KLM+14] Michael Kapralov Yin Tat Lee Cameron Musco Christopher Musco and Aaron Sidford. Single pass spectral sparsification in dynamic streams."},{"key":"e_1_3_2_1_23_1","unstructured":"FOCS 2014.  FOCS 2014."},{"key":"e_1_3_2_1_24_1","volume-title":"CCC","author":"Kannan Sampath","year":"2018","unstructured":"[KMY18] Sampath Kannan , Elchanan Mossel , and Grigory Yaroslavtsev . Linear sketching over F2 . CCC , 2018 . [KMY18] Sampath Kannan, Elchanan Mossel, and Grigory Yaroslavtsev. Linear sketching over F2. CCC, 2018."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_70"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039802"},{"key":"e_1_3_2_1_27_1","volume-title":"Separations and equivalences between turnstile streaming and linear sketching. CoRR, abs\/","author":"Kallaugher John","year":"1905","unstructured":"[KP20] John Kallaugher and Eric Price . Separations and equivalences between turnstile streaming and linear sketching. CoRR, abs\/ 1905 .02358, 2020. [KP20] John Kallaugher and Eric Price. Separations and equivalences between turnstile streaming and linear sketching. CoRR, abs\/ 1905.02358, 2020."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591812"},{"key":"e_1_3_2_1_29_1","unstructured":"[Nis92] Noam Nisan. Pseudorandom generators for space-bounded computation.  [Nis92] Noam Nisan. Pseudorandom generators for space-bounded computation."},{"key":"e_1_3_2_1_30_1","volume-title":"449-461","year":"1992","unstructured":"Combinatorica, 12 ( 4 ) : 449-461 , 1992 . Combinatorica, 12 ( 4 ): 449-461, 1992."},{"key":"e_1_3_2_1_31_1","first-page":"1844","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Nelson Jelani","unstructured":"[NY19] Jelani Nelson and Huacheng Yu . Optimal lower bounds for distributed and streaming spanning forest computation . In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1844 - 1860 . [NY19] Jelani Nelson and Huacheng Yu. Optimal lower bounds for distributed and streaming spanning forest computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1844-1860."},{"key":"e_1_3_2_1_32_1","unstructured":"SIAM 2019.  SIAM 2019."},{"key":"e_1_3_2_1_33_1","volume-title":"Colorful triangle counting and a mapreduce implementation. Information Processing Letters, 112 ( 7 ): 277-281","author":"Pagh Rasmus","year":"2012","unstructured":"[PT12] Rasmus Pagh and Charalampos E Tsourakakis . Colorful triangle counting and a mapreduce implementation. Information Processing Letters, 112 ( 7 ): 277-281 , 2012 . [PT12] Rasmus Pagh and Charalampos E Tsourakakis. Colorful triangle counting and a mapreduce implementation. Information Processing Letters, 112 ( 7 ): 277-281, 2012."},{"key":"e_1_3_2_1_34_1","unstructured":"[PTTW13] A. Pavan Kanat Tangwongsan Srikanta Tirthapura and Kun-Lung Wu.  [PTTW13] A. Pavan Kanat Tangwongsan Srikanta Tirthapura and Kun-Lung Wu."},{"key":"e_1_3_2_1_35_1","volume-title":"Proc. VLDB Endow., 6 ( 14 )","author":"Counting","year":"2013","unstructured":"Counting and sampling triangles from a graph stream . Proc. VLDB Endow., 6 ( 14 ) : 1870-1881, September 2013 . Counting and sampling triangles from a graph stream. Proc. VLDB Endow., 6 ( 14 ): 1870-1881, September 2013."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2012.6283954"},{"key":"e_1_3_2_1_37_1","unstructured":"[TKMF09] Charalampos E Tsourakakis U Kang Gary L Miller and Christos Faloutsos.  [TKMF09] Charalampos E Tsourakakis U Kang Gary L Miller and Christos Faloutsos."},{"key":"e_1_3_2_1_38_1","first-page":"837","volume-title":"Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining","author":"Doulion","year":"2009","unstructured":"Doulion : counting triangles in massive graphs with a coin . In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining , pages 837 - 846 . ACM, 2009 . Doulion: counting triangles in massive graphs with a coin. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 837-846. ACM, 2009."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384278","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384278","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384278"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":38,"alternative-id":["10.1145\/3357713.3384278","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384278","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}