default search action
David P. Woodruff
- > Home > Persons > David P. Woodruff
Publications
- 2025
- [j44]David P. Woodruff
, Shenghao Xie
Perfect Sampling in Turnstile Streams Beyond Small Moments. Proc. ACM Manag. Data 3(2): 106:1-106:27 (2025) - [c283]Elena Gribelyuk
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness. STOC 2025: 395-406 - [i246]Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou:
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness. CoRR abs/2503.19629 (2025) - [i245]David P. Woodruff, Shenghao Xie
Perfect Sampling in Turnstile Streams Beyond Small Moments. CoRR abs/2504.07237 (2025) - [i243]Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou:
Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings. CoRR abs/2504.16229 (2025) - [i237]Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas, David P. Woodruff, Samson Zhou:
On Fine-Grained Distinct Element Estimation. CoRR abs/2506.22608 (2025) - [i232]Vincent Cohen-Addad, David P. Woodruff, Shenghao Xie, Samson Zhou:
Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams. CoRR abs/2510.18180 (2025) - [i231]Honghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, Samson Zhou:
Lp Sampling in Distributed Data Streams with Applications to Adversarial Robustness. CoRR abs/2510.22816 (2025) - 2024
- [j42]Rajesh Jayaram
Streaming Algorithms with Few State Changes. Proc. ACM Manag. Data 2(2): 82 (2024) - [c280]Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou:
A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches. FOCS 2024: 2318-2343 - [c266]Zhao Song, Ali Vakilian, David P. Woodruff, Samson Zhou:
On Socially Fair Low-Rank Approximation and Column Subset Selection. NeurIPS 2024 - [c261]David P. Woodruff, Samson Zhou:
Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters. NeurIPS 2024 - [i220]Rajesh Jayaram, David P. Woodruff, Samson Zhou:
Streaming Algorithms with Few State Changes. CoRR abs/2406.06821 (2024) - [i213]Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou:
A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches. CoRR abs/2409.16153 (2024) - [i207]David P. Woodruff, Samson Zhou:
Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters. CoRR abs/2412.05807 (2024) - [i206]Zhao Song, Ali Vakilian, David P. Woodruff, Samson Zhou:
On Socially Fair Low-Rank Approximation and Column Subset Selection. CoRR abs/2412.06063 (2024) - 2023
- [c254]Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou:
On Differential Privacy and Adaptive Data Analysis with Bounded Space. EUROCRYPT (3) 2023: 35-65 - [c253]Vincent Cohen-Addad, David P. Woodruff, Samson Zhou:
Streaming Euclidean k-median and k-means with o(log n) Space. FOCS 2023: 883-908 - [c250]Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou:
Robust Algorithms on Adaptive Inputs from Bounded Adversaries. ICLR 2023 - [c247]Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou:
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. ICML 2023: 34952-34977 - [c240]David P. Woodruff, Peilin Zhong, Samson Zhou:
Near-Optimal k-Clustering in the Sliding Window Model. NeurIPS 2023 - [c239]David P. Woodruff, Fred Zhang, Samson Zhou:
On Robust Streaming for Learning with Experts: Algorithms and Lower Bounds. NeurIPS 2023 - [c237]Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou:
Near-Linear Sample Complexity for Lp Polynomial Regression. SODA 2023: 3959-4025 - [c236]Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. SODA 2023: 4026-4049 - [i204]Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou:
On Differential Privacy and Adaptive Data Analysis with Bounded Space. CoRR abs/2302.05707 (2023) - [i203]David P. Woodruff, Fred Zhang, Samson Zhou:
Streaming Algorithms for Learning with Experts: Deterministic Versus Robust. CoRR abs/2303.01709 (2023) - [i199]Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou:
Robust Algorithms on Adaptive Inputs from Bounded Adversaries. CoRR abs/2304.07413 (2023) - [i194]Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou:
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. CoRR abs/2306.01869 (2023) - [i189]Vincent Cohen-Addad, David P. Woodruff, Samson Zhou:
Streaming Euclidean k-median and k-means with o(log n) Space. CoRR abs/2310.02882 (2023) - [i186]David P. Woodruff, Peilin Zhong, Samson Zhou:
Near-Optimal k-Clustering in the Sliding Window Model. CoRR abs/2311.00642 (2023) - [i181]Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou:
On Differential Privacy and Adaptive Data Analysis with Bounded Space. IACR Cryptol. ePrint Arch. 2023: 171 (2023) - 2022
- [c231]Sepideh Mahabadi, David P. Woodruff, Samson Zhou
Adaptive Sketches for Robust Regression with Importance Sampling. APPROX/RANDOM 2022: 31:1-31:21 - [c226]Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Learning-Augmented $k$-means Clustering. ICLR 2022 - [c225]Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou:
Fast Regression for Structured Inputs. ICLR 2022 - [c218]Michael Kapralov
Noisy Boolean Hidden Matching with Applications. ITCS 2022: 91:1-91:19 - [c216]Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou:
The White-Box Adversarial Data Stream Model. PODS 2022: 15-27 - [c215]Rajesh Jayaram, David P. Woodruff, Samson Zhou:
Truly Perfect Samplers for Data Streams and Sliding Windows. PODS 2022: 29-40 - [c214]Agniva Chowdhury, Aritra Bose
A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World. RECOMB 2022: 86-106 - [c209]Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou:
Memory bounds for the experts problem. STOC 2022: 1158-1171 - [i177]Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou:
Fast Regression for Structured Inputs. CoRR abs/2203.07557 (2022) - [i172]Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou:
The White-Box Adversarial Data Stream Model. CoRR abs/2204.09136 (2022) - [i171]Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou:
Memory Bounds for the Experts Problem. CoRR abs/2204.09837 (2022) - [i167]Sepideh Mahabadi, David P. Woodruff, Samson Zhou:
Adaptive Sketches for Robust Regression with Importance Sampling. CoRR abs/2207.07822 (2022) - [i162]Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou:
Near-Linear Sample Complexity for Lp Polynomial Regression. CoRR abs/2211.06790 (2022) - [i160]Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. CoRR abs/2211.09964 (2022) - 2021
- [c203]David P. Woodruff, Samson Zhou:
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. FOCS 2021: 1183-1196 - [c201]David P. Woodruff, Samson Zhou:
Separations for Estimating Large Frequency Moments on Data Streams. ICALP 2021: 112:1-112:21 - [c200]Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou:
Learning a Latent Simplex in Input Sparsity Time. ICLR 2021 - [i156]David P. Woodruff, Samson Zhou:
Separations for Estimating Large Frequency Moments on Data Streams. CoRR abs/2105.03773 (2021) - [i155]Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou:
Learning a Latent Simplex in Input-Sparsity Time. CoRR abs/2105.08005 (2021) - [i151]Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou:
Noisy Boolean Hidden Matching with Applications. CoRR abs/2107.02578 (2021) - [i141]Rajesh Jayaram, David P. Woodruff, Samson Zhou:
Truly Perfect Samplers for Data Streams and Sliding Windows. CoRR abs/2108.12017 (2021) - [i140]Jon Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Learning-Augmented k-means Clustering. CoRR abs/2110.14094 (2021) - 2020
- [c178]Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou:
Near Optimal Linear Algebra in the Online and Sliding Window Models. FOCS 2020: 517-528 - [c164]Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou:
Non-adaptive adaptive sampling on turnstile streams. STOC 2020: 1251-1264 - [i131]Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou:
Non-Adaptive Adaptive Sampling on Turnstile Streams. CoRR abs/2004.10969 (2020) - [i129]Agniva Chowdhury, Petros Drineas, David P. Woodruff, Samson Zhou:
Approximation Algorithms for Sparse Principal Component Analysis. CoRR abs/2006.12748 (2020) - [i119]David P. Woodruff, Samson Zhou:
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. CoRR abs/2011.07471 (2020) - 2018
- [c133]Vladimir Braverman, Elena Grigorescu
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. APPROX-RANDOM 2018: 7:1-7:22 - [i87]Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou:
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. CoRR abs/1805.00212 (2018) - [i86]Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou:
Near Optimal Linear Algebra in the Online and Sliding Window Models. CoRR abs/1805.03765 (2018)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-11-16 00:30 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: