{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T16:10:34Z","timestamp":1762963834616,"version":"3.45.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"5","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2413849, 2413848"],"award-info":[{"award-number":["2413849, 2413848"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001409","name":"Department of Science and Technology, Ministry of Science and Technology, India","doi-asserted-by":"publisher","award":["TPN-104427"],"award-info":[{"award-number":["TPN-104427"]}],"id":[{"id":"10.13039\/501100001409","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,11,10]]},"abstract":"<jats:p>\n                    In this work, we study the notion of\n                    <jats:italic toggle=\"yes\">representation obliviousness<\/jats:italic>\n                    in the context of pseudodeterministic streaming algorithms. A (randomized) streaming algorithm A is pseudodeterministic, if for every stream D, there is a ''canonical value'' g(D) so that with probability at least 2\/3, A on input stream D outputs g(D). Intuitively, a randomized algorithm is representation oblivious if the output distribution of the algorithm does not depend on the representation of the input. We investigate this notion in the context of streaming algorithms, more specifically, distinct elements estimation (F\n                    <jats:sub>0<\/jats:sub>\n                    estimation) in data streams. In this context, representation obliviousness captures the idea that the output distribution of an algorithm for estimating F\n                    <jats:sub>0<\/jats:sub>\n                    should only depend on the set of distinct elements of the stream. This is a natural notion, as we note that standard streaming algorithms are representation-oblivious in this sense. We prove that any representation oblivious pseudodeterministic streaming algorithm for estimating F\n                    <jats:sub>0<\/jats:sub>\n                    must use \u03a9(n) space, where [n] is the universe. More generally, we prove that any representation oblivious pseudodeterministic t(n)-pass streaming algorithm requires \u03a9(n\/t(n)) space. This lower bound matches the space requirement of the straightforward multi-pass deterministic algorithm that exactly computes F\n                    <jats:sub>0<\/jats:sub>\n                    .\n                  <\/jats:p>","DOI":"10.1145\/3767718","type":"journal-article","created":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T15:06:02Z","timestamp":1762959962000},"page":"1-17","source":"Crossref","is-referenced-by-count":0,"title":["Representation Obliviousness and Pseudodeterminism in Streaming Algorithms"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-2042-1788","authenticated-orcid":false,"given":"Michael","family":"Chen","sequence":"first","affiliation":[{"name":"Iowa State University, Ames, IA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9518-6204","authenticated-orcid":false,"given":"Sourav","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"Indian Statistical Institute, Kolkata, WB, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1665-5266","authenticated-orcid":false,"given":"A.","family":"Pavan","sequence":"additional","affiliation":[{"name":"Iowa State University, Ames, IA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7959-4662","authenticated-orcid":false,"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[{"name":"University of Nebraska-Lincoln, Lincoln, NE, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,11,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.54"},{"volume-title":"Randomization and Approximation Techniques in Computer Science, Jos\u00e9 D","author":"Bar-Yossef Ziv","key":"e_1_2_1_3_1","unstructured":"Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan. 2002. Counting Distinct Elements in a Data Stream. In Randomization and Approximation Techniques in Computer Science, Jos\u00e9 D. P. Rolim and Salil Vadhan (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 1-10."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2023.30"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00044"},{"key":"e_1_2_1_6_1","first-page":"1","article-title":"Optimal Streaming and Tracking Distinct Elements with High Probability","volume":"16","author":"Blasiok Jaroslaw","year":"2018","unstructured":"Jaroslaw Blasiok. 2018. Optimal Streaming and Tracking Distinct Elements with High Probability. ACM Transactions on Algorithms (TALG), Vol. 16 (2018), 1 - 28. https:\/\/api.semanticscholar.org\/CorpusID:4605219","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2018.55"},{"key":"e_1_2_1_8_1","unstructured":"Amit Chakrabarti. 2023. Data Stream Algorithms Lecture Notes. https:\/\/www.cs.dartmouth.edu\/ac\/Teach\/data-streams-lecnotes.pdf"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2024.28"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2022.34"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2018.61"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.66"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520043"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1813695.1813720"},{"key":"e_1_2_1_16_1","volume-title":"Electronic Colloquium on Computational Complexity (ECCC)","volume":"18","author":"Gat Eran","year":"2011","unstructured":"Eran Gat and Shafi Goldwasser. 2011. Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications. Electronic Colloquium on Computational Complexity (ECCC), Vol. 18 (01 2011), 136."},{"key":"e_1_2_1_17_1","volume-title":"Unambiguous parity-query complexity. Electron. Colloquium Comput. Complex","author":"Gavinsky Dmytro","year":"2024","unstructured":"Dmytro Gavinsky. 2024. Unambiguous parity-query complexity. Electron. Colloquium Comput. Complex., Vol. TR24-009 (2024). showeprint[ECCC]TR24-009 https:\/\/eccc.weizmann.ac.il\/report\/2024\/009"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378687"},{"key":"e_1_2_1_19_1","volume-title":"Multi-pseudodeterministic algorithms. Electron. Colloquium Comput. Complex","author":"Goldreich Oded","year":"2019","unstructured":"Oded Goldreich. 2019. Multi-pseudodeterministic algorithms. Electron. Colloquium Comput. Complex., Vol. TR19-012 (2019). showeprint[ECCC]TR19-012 https:\/\/eccc.weizmann.ac.il\/report\/2019\/012"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422453"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.87"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.17"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.79"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00091"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519973"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591812"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451085"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359627"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX\/RANDOM.2024.26"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90157-D"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055500"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M10.1016\/0304-3975(92)90260-M"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3767718","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T16:08:39Z","timestamp":1762963719000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3767718"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,10]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,11,10]]}},"alternative-id":["10.1145\/3767718"],"URL":"https:\/\/doi.org\/10.1145\/3767718","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,11,10]]}}}