{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:46:22Z","timestamp":1781077582856,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","funder":[{"name":"NSF","award":["CCF-2339942, CCF-2335412, CCF-2335411"],"award-info":[{"award-number":["CCF-2339942, CCF-2335412, CCF-2335411"]}]},{"name":"Simons Foundation","award":[""],"award-info":[{"award-number":[""]}]},{"name":"CMU Paul and James Wang Sercomm Presidential Graduate Fellowship","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718227","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"395-406","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-2731-6658","authenticated-orcid":false,"given":"Elena","family":"Gribelyuk","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-5162-3328","authenticated-orcid":false,"given":"Honghao","family":"Lin","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2158-1380","authenticated-orcid":false,"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1450-1896","authenticated-orcid":false,"given":"Huacheng","family":"Yu","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8288-5698","authenticated-orcid":false,"given":"Samson","family":"Zhou","sequence":"additional","affiliation":[{"name":"Texas A&M University, College Station, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"2016","volume-title":"Chic. J. Theor. Comput. Sci.","author":"Aggarwal Divesh","year":"2016","unstructured":"Divesh Aggarwal and Oded Regev. 2016. A Note on Discrete Gaussian Combinations of Lattice Vectors. Chic. J. Theor. Comput. Sci., 2016 (2016)."},{"key":"e_1_3_2_1_2_1","volume-title":"Advances in Cryptology - ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I. 97\u2013116.","author":"Agrawal Shweta","unstructured":"Shweta Agrawal, Craig Gentry, Shai Halevi, and Amit Sahai. 2013. Discrete Gaussian Leftover Hash Lemma over Infinite Domains. In Advances in Cryptology - ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I. 97\u2013116."},{"key":"e_1_3_2_1_3_1","first-page":"1","article-title":"New Characterizations in Turnstile Streams with Applications. In 31st Conference on Computational Complexity","volume":"20","author":"Ai Yuqing","year":"2016","unstructured":"Yuqing Ai, Wei Hu, Yi Li, and David P. Woodruff. 2016. New Characterizations in Turnstile Streams with Applications. In 31st Conference on Computational Complexity, CCC. 20:1\u201320:22.","journal-title":"CCC."},{"key":"e_1_3_2_1_4_1","volume-title":"International Conference on Management of Data. 15\u201327","author":"Ajtai Mikl\u00f3s","year":"2022","unstructured":"Mikl\u00f3s Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, and Samson Zhou. 2022. The White-Box Adversarial Data Stream Model. In PODS \u201922: International Conference on Management of Data. 15\u201327."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451041"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588681"},{"key":"e_1_3_2_1_8_1","first-page":"1","article-title":"A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators. In 14th Innovations in Theoretical Computer Science Conference","volume":"8","author":"Attias Idan","year":"2023","unstructured":"Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. 2023. A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators. In 14th Innovations in Theoretical Computer Science Conference, ITCS. 8:1\u20138:19.","journal-title":"ITCS."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-024-01259-8"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330911"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520064"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977066.15"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498334"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387643"},{"key":"e_1_3_2_1_15_1","volume-title":"Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS. 3544\u20133557","author":"Braverman Vladimir","year":"2021","unstructured":"Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. 2021. Adversarial Robustness of Streaming Algorithms through Importance Sampling. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS. 3544\u20133557."},{"key":"e_1_3_2_1_16_1","first-page":"1","article-title":"Adversarially Robust Coloring for Graph Streams. In 13th Innovations in Theoretical Computer Science Conference","volume":"37","author":"Chakrabarti Amit","year":"2022","unstructured":"Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. 2022. Adversarially Robust Coloring for Graph Streams. In 13th Innovations in Theoretical Computer Science Conference, ITCS. 37:1\u201337:23.","journal-title":"ITCS."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_3_2_1_18_1","volume-title":"The Eleventh International Conference on Learning Representations, ICLR.","author":"Cherapanamjeri Yeshwanth","year":"2023","unstructured":"Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou. 2023. Robust Algorithms on Adaptive Inputs from Bounded Adversaries. In The Eleventh International Conference on Learning Representations, ICLR."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_3_2_1_20_1","volume-title":"Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part III. 35\u201365.","author":"Dinur Itai","unstructured":"Itai Dinur, Uri Stemmer, David P. Woodruff, and Samson Zhou. 2023. On Differential Privacy and Adaptive Data Analysis with Bounded Space. In Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part III. 35\u201365."},{"key":"e_1_3_2_1_21_1","first-page":"1","article-title":"High Probability Frequency Moment Sketches. In 45th International Colloquium on Automata, Languages, and Programming","volume":"58","author":"Ganguly Sumit","year":"2018","unstructured":"Sumit Ganguly and David P. Woodruff. 2018. High Probability Frequency Moment Sketches. In 45th International Colloquium on Automata, Languages, and Programming, ICALP. 58:1\u201358:15.","journal-title":"ICALP."},{"key":"e_1_3_2_1_22_1","first-page":"1","article-title":"Pseudo-Deterministic Streaming. In 11th Innovations in Theoretical Computer Science Conference","volume":"79","author":"Goldwasser Shafi","year":"2020","unstructured":"Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, and David P. Woodruff. 2020. Pseudo-Deterministic Streaming. In 11th Innovations in Theoretical Computer Science Conference, ITCS. 79:1\u201379:25.","journal-title":"ITCS."},{"key":"e_1_3_2_1_23_1","volume-title":"65th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 2318\u20132343","author":"Gribelyuk Elena","year":"2024","unstructured":"Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou. 2024. A Strong Separation for Adversarially Robust L_0 Estimation for Linear Sketches. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 2318\u20132343."},{"key":"e_1_3_2_1_24_1","unstructured":"Elena Gribelyuk Honghao Lin David P. Woodruff Huacheng Yu and Samson Zhou. 2025. Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness. arxiv:2503.19629. arxiv:2503.19629"},{"key":"e_1_3_2_1_25_1","volume-title":"Symposium on Theory of Computing Conference, STOC. 121\u2013130","author":"Hardt Moritz","unstructured":"Moritz Hardt and David P. Woodruff. 2013. How robust are linear sketches to adaptive inputs? In Symposium on Theory of Computing Conference, STOC. 121\u2013130."},{"key":"e_1_3_2_1_26_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS.","author":"Hassidim Avinatan","year":"2020","unstructured":"Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. 2020. Adversarially Robust Streaming Algorithms via Differential Privacy. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483706"},{"key":"e_1_3_2_1_28_1","volume-title":"The Complexity of Dynamic Least-Squares Regression. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 1605\u20131627","author":"Jiang Shunhua","year":"2023","unstructured":"Shunhua Jiang, Binghui Peng, and Omri Weinstein. 2023. The Complexity of Dynamic Least-Squares Regression. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 1605\u20131627."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384278"},{"key":"e_1_3_2_1_31_1","volume-title":"CRYPTO Proceedings, Part III. 94\u2013121","author":"Kaplan Haim","year":"2021","unstructured":"Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. 2021. Separating Adaptive Streaming from Oblivious Streaming Using the Bounded Storage Model. In Advances in Cryptology - CRYPTO - 41st Annual International Cryptology Conference, CRYPTO Proceedings, Part III. 94\u2013121."},{"key":"e_1_3_2_1_32_1","volume-title":"Symposium on Theory of Computing, STOC. 174\u2013183","author":"Li Yi","unstructured":"Yi Li, Huy L. Nguyen, and David P. Woodruff. 2014. Turnstile streaming algorithms might as well be linear sketches. In Symposium on Theory of Computing, STOC. 174\u2013183."},{"key":"e_1_3_2_1_33_1","volume-title":"Woodruff","author":"Li Yi","year":"2013","unstructured":"Yi Li and David P. Woodruff. 2013. A Tight Lower Bound for High Frequency Moment Estimation with Small Error. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM. Proceedings. 623\u2013638."},{"key":"e_1_3_2_1_34_1","first-page":"1","article-title":"Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"39","author":"Li Yi","year":"2016","unstructured":"Yi Li and David P. Woodruff. 2016. Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM. 39:1\u201339:11.","journal-title":"APPROX\/RANDOM."},{"key":"e_1_3_2_1_35_1","volume-title":"Testing Positive Semidefiniteness Using Linear Measurements. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS","author":"Needell Deanna","year":"2022","unstructured":"Deanna Needell, William Swartworth, and David P. Woodruff. 2022. Testing Positive Semidefiniteness Using Linear Measurements. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022. 87\u201397."},{"key":"e_1_3_2_1_36_1","volume-title":"IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS. 295\u2013304","author":"Price Eric","unstructured":"Eric Price and David P. Woodruff. 2011. (1 + eps)-Approximate Sparse Recovery. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS. 295\u2013304."},{"key":"e_1_3_2_1_37_1","volume-title":"Woodruff","author":"Price Eric","year":"2013","unstructured":"Eric Price and David P. Woodruff. 2013. Lower Bounds for Adaptive Sparse Recovery. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 652\u2013663."},{"key":"e_1_3_2_1_38_1","volume-title":"An introduction. Graduate Texts in Mathematics, 201","author":"Silverman Joseph H","year":"2000","unstructured":"Joseph H Silverman and Marc Hindry. 2000. Diophantine geometry, An introduction. Graduate Texts in Mathematics, 201 (2000)."},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC. 145\u2013155","author":"Swartworth William","unstructured":"William Swartworth and David P. Woodruff. 2023. Optimal Eigenvalue Approximation via Sketching. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC. 145\u2013155."},{"key":"e_1_3_2_1_40_1","first-page":"1","article-title":"Separations for Estimating Large Frequency Moments on Data Streams. In 48th International Colloquium on Automata, Languages, and Programming","volume":"112","author":"Woodruff David P.","year":"2021","unstructured":"David P. Woodruff and Samson Zhou. 2021. Separations for Estimating Large Frequency Moments on Data Streams. In 48th International Colloquium on Automata, Languages, and Programming, ICALP. 112:1\u2013112:21.","journal-title":"ICALP."},{"key":"e_1_3_2_1_41_1","volume-title":"62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS. 1183\u20131196","author":"David","unstructured":"David P. Woodruff and Samson Zhou. 2021. Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS. 1183\u20131196."},{"key":"e_1_3_2_1_42_1","volume-title":"Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems, NeurIPS.","author":"David","unstructured":"David P. Woodruff and Samson Zhou. 2024. Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems, NeurIPS."},{"key":"e_1_3_2_1_43_1","unstructured":"Banff 2014 Workshop. 2014. Communication Complexity and Applications. https:\/\/www.birs.ca\/events\/2014\/5-day-workshops\/14w5164\/videos\/watch\/201408251453-Woodruff.html"},{"key":"e_1_3_2_1_44_1","unstructured":"Banff 2017 Workshop. 2017. Communication Complexity and Applications II. https:\/\/www.birs.ca\/events\/2017\/5-day-workshops\/17w5147\/videos\/watch\/201703231016-Woodruff.html"},{"key":"e_1_3_2_1_45_1","unstructured":"FOCS 2023 Workshop. 2023. Exploring the Frontiers of Adaptive Robustness. https:\/\/samsonzhou.github.io\/focs-2023-workshop-adaptive-robustness"},{"key":"e_1_3_2_1_46_1","unstructured":"STOC 2021 Workshop. 2021. Robust Streaming Sketching and Sampling. https:\/\/rajeshjayaram.com\/stoc-2021-robust-streaming-workshop.html"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718227","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:44:55Z","timestamp":1750693495000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":46,"alternative-id":["10.1145\/3717823.3718227","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718227","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}