David P. Woodruff

614 papers A* 225A 35B 5Journal 308Unranked 38

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Accelerating Scientific Research with Gemini: Case Studies and Common Techniques. CoRR David P. Woodruff, Vincent Cohen-Addad, Lalit Jain, Jieming Mao, Song Zuo, MohammadHossein Bateni, Simina Brânzei, Michael P. Brenner, Lin Chen, Ying Feng, Lance Fortnow, Gang Fu, Ziyi Guan, Zahra Hadizadeh, Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Adel Javanmard, Karthik C. S., Ken-ichi Kawarabayashi, Ravi Kumar, Silvio Lattanzi, Euiwoong Lee, Yi Li, Ioannis Panageas, Dimitris Paparas, Benjamin Przybocki, Bernardo Subercaseaux, Ola Svensson, Shayan Taherijam, Xuan Wu, Eylon Yogev, Morteza Zadimoghaddam, Samson Zhou, Yossi Matias, James Manyika, Vahab Mirrokni
2026	J	`jnl`	Adversarial Robustness on Insertion-Deletion Streams. CoRR Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou
2026	J	`jnl`	Aletheia tackles FirstProof autonomously. CoRR Tony Feng, Junehyuk Jung, Sang-hyun Kim, Carlo Pagano, Sergei Gukov, Cheng-Chiang Tsai, David P. Woodruff, Adel Javanmard, Aryan Mokhtari, Dawsen Hwang, Yuri Chervonyi, Jonathan N. Lee, Garrett Bingham, Trieu H. Trinh, Vahab Mirrokni, Quoc V. Le, Thang Luong
2026	J	`jnl`	Better Bounds for the Distributed Experts Problem. CoRR David P. Woodruff, Samson Zhou
2026	J	`jnl`	Consistent Low-Rank Approximation. CoRR David P. Woodruff, Samson Zhou
2026	J	`jnl`	Distributed Algorithms for Euclidean Clustering. CoRR Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou
2026	A*	`conf`	L SODA Honghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, Samson Zhou
2026	J	`jnl`	Learning-Augmented Moment Estimation on Time-Decay Models. CoRR Soham Nagawanshi, Shalini Panthangi, Chen Wang, David P. Woodruff, Samson Zhou
2026	A*	`conf`	Online Learning with Limited Information in the Sliding Window Model. SODA Vladimir Braverman, Sumegha Garg, Chen Wang, David P. Woodruff, Samson Zhou
2026	J	`jnl`	Online Learning with Limited Information in the Sliding Window Model. CoRR Vladimir Braverman, Sumegha Garg, Chen Wang, David P. Woodruff, Samson Zhou
2026	J	`jnl`	Progress on the Courtade-Kumar Conjecture: Optimal High-Noise Entropy Bounds and Generalized Coordinate-wise Mutual Information. CoRR Adel Javanmard, David P. Woodruff
2026	J	`jnl`	Solving an Open Problem in Theoretical Physics using AI-Assisted Discovery. CoRR Michael P. Brenner, Vincent Cohen-Addad, David P. Woodruff
2025	A*	`conf`	Beyond Worst-Case Dimensionality Reduction for Sparse Vectors. ICLR Sandeep Silwal, David P. Woodruff, Qiuyi Zhang
2025	J	`jnl`	Beyond Worst-Case Dimensionality Reduction for Sparse Vectors. CoRR Sandeep Silwal, David P. Woodruff, Qiuyi Zhang
2025	J	`jnl`	Combinatorial Optimization using Comparison Oracles. CoRR Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider, David P. Woodruff
2025	J	`jnl`	Communication Bounds for the Distributed Experts Problem. CoRR Zhihao Jia, Qi Pang, Trung Tran, David P. Woodruff, Zhihao Zhang, Wenting Zheng
2025	J	`jnl`	Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings. CoRR Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou
2025	J	`jnl`	Finding Heavy-Hitters with Optimal State Changes. Proc. ACM Manag. Data William Swartworth, David P. Woodruff
2025	A*	`conf`	Guessing Efficiently for Constrained Subspace Approximation. ICALP Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu, Ali Vakilian, David P. Woodruff
2025	J	`jnl`	Guessing Efficiently for Constrained Subspace Approximation. CoRR Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu, Ali Vakilian, David P. Woodruff
2025	J	`jnl`	JEPA-Reasoner: Decoupling Latent Reasoning from Token Generation. CoRR Bingyang Kelvin Liu, Ziyu Patrick Chen, David P. Woodruff
2025	J	`jnl`	John Ellipsoids via Lazy Updates. CoRR David P. Woodruff, Taisuke Yasuda
2025	J	`jnl`	L CoRR Honghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, Samson Zhou
2025	A*	`conf`	LevAttention: Time, Space and Streaming Efficient Algorithm for Heavy Attentions. ICLR Ravindran Kannan, Chiranjib Bhattacharyya, Praneeth Kacham, David P. Woodruff
2025	A*	`conf`	Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness. STOC Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou
2025	J	`jnl`	Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness. CoRR Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou
2025	A*	`conf`	Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures. ICML Alina Ene, Alessandro Epasto, Vahab Mirrokni, Hoai-An Nguyen, Huy L. Nguyen, David P. Woodruff, Peilin Zhong
2025	J	`jnl`	Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures. CoRR Alina Ene, Alessandro Epasto, Vahab Mirrokni, Hoai-An Nguyen, Huy L. Nguyen, David P. Woodruff, Peilin Zhong
2025	A	`conf`	Multipass Linear Sketches for Geometric LP-Type Problems. APPROX/RANDOM N. Efe Çekirge, William Gay, David P. Woodruff
2025	J	`jnl`	Multipass Linear Sketches for Geometric LP-Type Problems. CoRR N. Efe Çekirge, William Gay, David P. Woodruff
2025	J	`jnl`	Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams. CoRR Vincent Cohen-Addad, David P. Woodruff, Shenghao Xie, Samson Zhou
2025	A*	`conf`	On Differential Privacy for Adaptively Solving Search Problems via Sketching. ICML Shiyuan Feng, Ying Feng, George Zhaoqi Li, Zhao Song, David P. Woodruff, Lichen Zhang
2025	J	`jnl`	On Differential Privacy for Adaptively Solving Search Problems via Sketching. CoRR Shiyuan Feng, Ying Feng, George Z. Li, Zhao Song, David P. Woodruff, Lichen Zhang
2025	A*	`conf`	On Fine-Grained Distinct Element Estimation. ICML Ilias Diakonikolas, Daniel Kane, Jasper C. H. Lee, Thanasis Pittas, David P. Woodruff, Samson Zhou
2025	J	`jnl`	On Fine-Grained Distinct Element Estimation. CoRR Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas, David P. Woodruff, Samson Zhou
2025	J	`jnl`	On Sketching Trimmed Statistics. CoRR Honghao Lin, Hoai-An Nguyen, David P. Woodruff
2025	J	`jnl`	Online Lewis Weight Sampling. ACM Trans. Algorithms David P. Woodruff, Taisuke Yasuda
2025	J	`jnl`	Perfect L CoRR William Swartworth, David P. Woodruff, Samson Zhou
2025	A*	`conf`	Perfect Lp Sampling with Polylogarithmic Update Time. FOCS William Swartworth, David P. Woodruff, Samson Zhou
2025	J	`jnl`	Perfect Sampling in Turnstile Streams Beyond Small Moments. CoRR David P. Woodruff, Shenghao Xie, Samson Zhou
2025	J	`jnl`	Perfect Sampling in Turnstile Streams Beyond Small Moments. Proc. ACM Manag. Data David P. Woodruff, Shenghao Xie, Samson Zhou
2025	J	`jnl`	Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph. CoRR Gautam Kamath, Alireza F. Pour, Matthew Regehr, David P. Woodruff
2025	A*	`conf`	Range Counting Oracles for Geometric Problems. SoCG Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, David P. Woodruff
2025	J	`jnl`	Range Counting Oracles for Geometric Problems. CoRR Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, David P. Woodruff
2025	A*	`conf`	Robust Sparsification via Sensitivity. ICML Chansophea Wathanak In, Yi Li, David P. Woodruff, Xuan Wu
2025	A*	`conf`	Root Ridge Leverage Score Sampling for ℓp Subspace Approximation. FOCS David P. Woodruff, Taisuke Yasuda
2025	A	`conf`	Space Complexity of Minimum Cut Problems in Single-Pass Streams. ITCS Matthew Ding, Alexandro Garces, Jason Li, Honghao Lin, Jelani Nelson, Vihan Shah, David P. Woodruff
2025	A*	`conf`	Streaming Algorithms For ℓp Flows and ℓp Regression. ICLR Amit Chakrabarti, Jeffrey Jiang, David P. Woodruff, Taisuke Yasuda
2025	J	`jnl`	Sublinear Time Quantum Sensitivity Sampling. CoRR Zhao Song, David P. Woodruff, Lichen Zhang
2025	A*	`conf`	Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model. ICALP Shiyuan Feng, William Swartworth, David P. Woodruff
2025	J	`jnl`	Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model. CoRR Shiyuan Feng, William Swartworth, David P. Woodruff
2025	A*	`conf`	Tight Sampling Bounds for Eigenvalue Approximation. SODA William Swartworth, David P. Woodruff
2025	J	`jnl`	Unbiased Insights: Optimal Streaming Algorithms for ℓ CoRR Honghao Lin, Hoai-An Nguyen, William Swartworth, David P. Woodruff
2025	A*	`conf`	Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra. ICML Raphael A. Meyer, William J. Swartworth, David P. Woodruff
2025	J	`jnl`	Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra. CoRR Raphael A. Meyer, William Swartworth, David P. Woodruff
2024	A*	`conf`	A New Information Complexity Measure for Multi-pass Streaming with Applications. STOC Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang
2024	J	`jnl`	A New Information Complexity Measure for Multi-pass Streaming with Applications. CoRR Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang
2024	J	`jnl`	A Strong Separation for Adversarially Robust ℓ CoRR Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou
2024	A*	`conf`	A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches. FOCS Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou
2024	J	`jnl`	A Theory for Compressibility of Graph Transformers for Transductive Learning. CoRR Hamed Shirzad, Honghao Lin, Ameya Velingker, Balaji Venkatachalam, David P. Woodruff, Danica J. Sutherland
2024	A*	`conf`	Adaptive Regret for Bandits Made Possible: Two Queries Suffice. ICLR Zhou Lu, Qiuyi Zhang, Xinyi Chen, Fred Zhang, David P. Woodruff, Elad Hazan
2024	J	`jnl`	Adaptive Regret for Bandits Made Possible: Two Queries Suffice. CoRR Zhou Lu, Qiuyi Zhang, Xinyi Chen, Fred Zhang, David P. Woodruff, Elad Hazan
2024	A*	`conf`	Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters. NeurIPS David P. Woodruff, Samson Zhou
2024	J	`jnl`	Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters. CoRR David P. Woodruff, Samson Zhou
2024	A*	`conf`	Approximating the Top Eigenvector in Random Order Streams. NeurIPS Praneeth Kacham, David P. Woodruff
2024	J	`jnl`	Approximating the Top Eigenvector in Random Order Streams. CoRR Praneeth Kacham, David P. Woodruff
2024	—	`conf`	Approximation Algorithms on Matrices - With Some Database Applications! PODS Companion David P. Woodruff
2024	A*	`conf`	Communication Bounds for the Distributed Experts Problem. NeurIPS Zhihao Jia, Qi Pang, Trung Tran, David P. Woodruff, Zhihao Zhang, Wenting Zheng
2024	J	`jnl`	Coresets for Multiple ℓ CoRR David P. Woodruff, Taisuke Yasuda
2024	A*	`conf`	Coresets for Multiple ℓp Regression. ICML David P. Woodruff, Taisuke Yasuda
2024	A*	`conf`	Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond. ICML Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, Michael Wunder
2024	J	`jnl`	Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond. CoRR Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, Michael Wunder
2024	A*	`conf`	Even Sparser Graph Transformers. NeurIPS Hamed Shirzad, Honghao Lin, Balaji Venkatachalam, Ameya Velingker, David P. Woodruff, Danica J. Sutherland
2024	J	`jnl`	Even Sparser Graph Transformers. CoRR Hamed Shirzad, Honghao Lin, Balaji Venkatachalam, Ameya Velingker, David P. Woodruff, Danica J. Sutherland
2024	J	`jnl`	Fast Sampling Based Sketches for Tensors. CoRR William Swartworth, David P. Woodruff
2024	A*	`conf`	Fast Sampling-Based Sketches for Tensors. ICML William J. Swartworth, David P. Woodruff
2024	A*	`conf`	Fast White-Box Adversarial Streaming Without a Random Oracle. ICML Ying Feng, Aayush Jain, David P. Woodruff
2024	J	`jnl`	Fast White-Box Adversarial Streaming Without a Random Oracle. CoRR Ying Feng, Aayush Jain, David P. Woodruff
2024	A	`conf`	Faster Algorithms for Schatten-p Low Rank Approximation. APPROX/RANDOM Praneeth Kacham, David P. Woodruff
2024	J	`jnl`	Faster Algorithms for Schatten-p Low Rank Approximation. CoRR Praneeth Kacham, David P. Woodruff
2024	A*	`conf`	GRASS: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients. EMNLP Aashiq Muhamed, Oscar Li, David P. Woodruff, Mona T. Diab, Virginia Smith
2024	J	`jnl`	Grass: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients. CoRR Aashiq Muhamed, Oscar Li, David P. Woodruff, Mona T. Diab, Virginia Smith
2024	A*	`conf`	High-Dimensional Geometric Streaming for Nearly Low Rank Data. ICML Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong
2024	J	`jnl`	High-Dimensional Geometric Streaming for Nearly Low Rank Data. CoRR Hossein Esfandiari, Vahab Mirrokni, Praneeth Kacham, David P. Woodruff, Peilin Zhong
2024	A*	`conf`	HyperAttention: Long-context Attention in Near-Linear Time. ICLR Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, Amir Zandieh
2024	A*	`conf`	Improving the Bit Complexity of Communication for Distributed Convex Optimization. STOC Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, Guanghao Ye
2024	J	`jnl`	Improving the Bit Complexity of Communication for Distributed Convex Optimization. CoRR Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, Guanghao Ye
2024	A*	`conf`	John Ellipsoids via Lazy Updates. NeurIPS David P. Woodruff, Taisuke Yasuda
2024	A*	`conf`	Learning Multiple Secrets in Mastermind. ICML Milind Prabhu, David P. Woodruff
2024	J	`jnl`	Learning Multiple Secrets in Mastermind. CoRR Milind Prabhu, David P. Woodruff
2024	J	`jnl`	LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions. CoRR Ravindran Kannan, Chiranjib Bhattacharyya, Praneeth Kacham, David P. Woodruff
2024	A	`conf`	Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions. ITCS Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang
2024	J	`jnl`	Nearly Linear Sparsification of ℓ CoRR David P. Woodruff, Taisuke Yasuda
2024	A*	`conf`	On Socially Fair Low-Rank Approximation and Column Subset Selection. NeurIPS Zhao Song, Ali Vakilian, David P. Woodruff, Samson Zhou
2024	J	`jnl`	On Socially Fair Low-Rank Approximation and Column Subset Selection. CoRR Zhao Song, Ali Vakilian, David P. Woodruff, Samson Zhou
2024	A*	`conf`	Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond. STOC Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong
2024	J	`jnl`	Optimal Communication for Classic Functions in the Coordinator Model and Beyond. CoRR Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong
2024	A*	`conf`	Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms. ICLR Yi Li, Honghao Lin, David P. Woodruff
2024	J	`jnl`	Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms. CoRR Yi Li, Honghao Lin, David P. Woodruff
2024	A*	`ed.`	Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024 SODA David P. Woodruff
2024	A*	`conf`	Reweighted Solutions for Weighted Low Rank Approximation. ICML David P. Woodruff, Taisuke Yasuda
2024	J	`jnl`	Reweighted Solutions for Weighted Low Rank Approximation. CoRR David P. Woodruff, Taisuke Yasuda
2024	J	`jnl`	Space Complexity of Minimum Cut Problems in Single-Pass Streams. CoRR Matthew Ding, Alexandro Garces, Jason Li, Honghao Lin, Jelani Nelson, Vihan Shah, David P. Woodruff
2024	A	`conf`	Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions. ITCS Justin Y. Chen, Piotr Indyk, David P. Woodruff
2024	J	`jnl`	Streaming Algorithms with Few State Changes. CoRR Rajesh Jayaram, David P. Woodruff, Samson Zhou
2024	J	`jnl`	Streaming Algorithms with Few State Changes. Proc. ACM Manag. Data Rajesh Jayaram, David P. Woodruff, Samson Zhou
2024	J	`jnl`	Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut. CoRR Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, Jason Zhang
2024	J	`jnl`	Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut. Proc. ACM Manag. Data Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, Jason Zhang
2024	J	`jnl`	Tight Sampling Bounds for Eigenvalue Approximation. CoRR William Swartworth, David P. Woodruff
2024	A	`conf`	Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. ITCS Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff
2023	A*	`conf`	Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression. ICLR Alexander Munteanu, Simon Omlor, David P. Woodruff
2023	J	`jnl`	Almost Linear Constant-Factor Sketching for 𝓁 CoRR Alexander Munteanu, Simon Omlor, David P. Woodruff
2023	A*	`conf`	Computing Approximate 𝓁 NeurIPS Swati Padmanabhan, David P. Woodruff, Richard Zhang
2023	J	`jnl`	Computing Approximate 𝓁 CoRR Swati Padmanabhan, David P. Woodruff, Qiuyi (Richard) Zhang
2023	A*	`conf`	Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. ICML Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou
2023	J	`jnl`	Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. CoRR Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou
2023	A*	`conf`	Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products. NeurIPS Tamás Sarlós, Xingyou Song, David P. Woodruff, Richard Zhang
2023	J	`jnl`	Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products. CoRR Tamás Sarlós, Xingyou Song, David P. Woodruff, Qiuyi Zhang
2023	J	`jnl`	HyperAttention: Long-context Attention in Near-Linear Time. CoRR Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, Amir Zandieh
2023	A*	`conf`	Improved Algorithms for White-Box Adversarial Streams. ICML Ying Feng, David P. Woodruff
2023	J	`jnl`	Improved Algorithms for White-Box Adversarial Streams. CoRR Ying Feng, David P. Woodruff
2023	A*	`conf`	Learning the Positions in CountSketch. ICLR Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David P. Woodruff
2023	J	`jnl`	Learning the Positions in CountSketch. CoRR Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David P. Woodruff
2023	A*	`conf`	Lower Bounds on Adaptive Sensing for Matrix Recovery. NeurIPS Praneeth Kacham, David P. Woodruff
2023	J	`jnl`	Lower Bounds on Adaptive Sensing for Matrix Recovery. CoRR Praneeth Kacham, David P. Woodruff
2023	A*	`conf`	Near-Linear Sample Complexity for SODA Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou
2023	A*	`conf`	Near-Optimal k-Clustering in the Sliding Window Model. NeurIPS David P. Woodruff, Peilin Zhong, Samson Zhou
2023	J	`jnl`	Near-Optimal k-Clustering in the Sliding Window Model. CoRR David P. Woodruff, Peilin Zhong, Samson Zhou
2023	A*	`conf`	New Subset Selection Algorithms for Low Rank Approximation: Offline and Online. STOC David P. Woodruff, Taisuke Yasuda
2023	J	`jnl`	New Subset Selection Algorithms for Low Rank Approximation: Offline and Online. CoRR David P. Woodruff, Taisuke Yasuda
2023	—	`conf`	On Differential Privacy and Adaptive Data Analysis with Bounded Space. EUROCRYPT (3) Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou
2023	J	`jnl`	On Differential Privacy and Adaptive Data Analysis with Bounded Space. CoRR Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou
2023	J	`jnl`	On Differential Privacy and Adaptive Data Analysis with Bounded Space. IACR Cryptol. ePrint Arch. Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou
2023	A*	`conf`	On Robust Streaming for Learning with Experts: Algorithms and Lower Bounds. NeurIPS David P. Woodruff, Fred Zhang, Samson Zhou
2023	A*	`conf`	Online Lewis Weight Sampling. SODA David P. Woodruff, Taisuke Yasuda
2023	A*	`conf`	Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. SODA Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou
2023	A*	`conf`	Optimal Eigenvalue Approximation via Sketching. STOC William Swartworth, David P. Woodruff
2023	J	`jnl`	Optimal Eigenvalue Approximation via Sketching. CoRR William Swartworth, David P. Woodruff
2023	A	`conf`	Optimal Sketching Bounds for Sparse Linear Regression. AISTATS Tung Mai, Alexander Munteanu, Cameron Musco, Anup Rao, Chris Schwiegelshohn, David P. Woodruff
2023	J	`jnl`	Optimal Sketching Bounds for Sparse Linear Regression. CoRR Tung Mai, Alexander Munteanu, Cameron Musco, Anup B. Rao, Chris Schwiegelshohn, David P. Woodruff
2023	A*	`conf`	Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming. FOCS Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff
2023	J	`jnl`	Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming. CoRR Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff
2023	J	`jnl`	Recovery From Non-Decomposable Distance Oracles. IEEE Trans. Inf. Theory Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang
2023	A	`conf`	Recovery from Non-Decomposable Distance Oracles. ITCS Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang
2023	A*	`conf`	Robust Algorithms on Adaptive Inputs from Bounded Adversaries. ICLR Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou
2023	J	`jnl`	Robust Algorithms on Adaptive Inputs from Bounded Adversaries. CoRR Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou
2023	J	`jnl`	Separating Theory Comput. Elbert Du, Michael Mitzenmacher, David P. Woodruff, Guang Yang
2023	A*	`conf`	Sharper Bounds for ℓ ICML David P. Woodruff, Taisuke Yasuda
2023	J	`jnl`	Sharper Bounds for 𝓁 CoRR David P. Woodruff, Taisuke Yasuda
2023	A*	`conf`	Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming. NeurIPS Gregory Dexter, Petros Drineas, David P. Woodruff, Taisuke Yasuda
2023	J	`jnl`	Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming. CoRR Gregory Dexter, Petros Drineas, David P. Woodruff, Taisuke Yasuda
2023	J	`jnl`	Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions. CoRR Justin Y. Chen, Piotr Indyk, David P. Woodruff
2023	J	`jnl`	Streaming Algorithms for Learning with Experts: Deterministic Versus Robust. CoRR David P. Woodruff, Fred Zhang, Samson Zhou
2023	A*	`conf`	Streaming Euclidean k-median and k-means with o(log n) Space. FOCS Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
2023	J	`jnl`	Streaming Euclidean k-median and k-means with o(log n) Space. CoRR Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
2023	J	`jnl`	Task-Based MoE for Multitask Multilingual Machine Translation. CoRR Hai Pham, Young Jin Kim, Subhabrata Mukherjee, David P. Woodruff, Barnabás Póczos, Hany Hassan Awadalla
2023	J	`jnl`	Technical Perspective: Tapping the Link between Algorithmic Model Counting and Streaming. Commun. ACM David P. Woodruff
2023	A*	`conf`	The ℓ SODA Yi Li, Honghao Lin, David P. Woodruff
2023	J	`jnl`	Towards Optimal Moment Estimation in Streaming and Distributed Models. ACM Trans. Algorithms Rajesh Jayaram, David P. Woodruff
2023	J	`jnl`	Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. CoRR Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff
2023	A*	`conf`	ℓ COLT Yi Li, Honghao Lin, David P. Woodruff
2023	J	`jnl`	𝓁 CoRR Yi Li, Honghao Lin, David P. Woodruff
2022	A*	`ed.`	49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, Paris, France, July 4-8, 2022 ICALP Mikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff
2022	B	`conf`	A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World. RECOMB Agniva Chowdhury, Aritra Bose, Samson Zhou, David P. Woodruff, Petros Drineas
2022	J	`jnl`	A Framework for Adversarially Robust Streaming Algorithms. J. ACM Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev
2022	A*	`conf`	Active Linear Regression for ℓp Norms and Beyond. FOCS Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda
2022	A	`conf`	Adaptive Sketches for Robust Regression with Importance Sampling. APPROX/RANDOM Sepideh Mahabadi, David P. Woodruff, Samson Zhou
2022	J	`jnl`	Adaptive Sketches for Robust Regression with Importance Sampling. CoRR Sepideh Mahabadi, David P. Woodruff, Samson Zhou
2022	A	`conf`	An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes. ITCS Anubhav Baweja, Justin Jia, David P. Woodruff
2022	J	`jnl`	Bounding the Width of Neural Networks via Coupled Initialization - A Worst Case Analysis. CoRR Alexander Munteanu, Simon Omlor, Zhao Song, David P. Woodruff
2022	A*	`conf`	Bounding the Width of Neural Networks via Coupled Initialization A Worst Case Analysis. ICML Alexander Munteanu, Simon Omlor, Zhao Song, David P. Woodruff
2022	A*	`conf`	Fast Regression for Structured Inputs. ICLR Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou
2022	J	`jnl`	Fast Regression for Structured Inputs. CoRR Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou
2022	A*	`conf`	Frequency Estimation with One-Sided Error. SODA Piotr Indyk, Shyam Narayanan, David P. Woodruff
2022	A*	`conf`	High-Dimensional Geometric Streaming in Polynomial Space. FOCS David P. Woodruff, Taisuke Yasuda
2022	J	`jnl`	High-Dimensional Geometric Streaming in Polynomial Space. CoRR David P. Woodruff, Taisuke Yasuda
2022	A*	`conf`	Improved Algorithms for Low Rank Approximation from Sparsity. SODA David P. Woodruff, Taisuke Yasuda
2022	A*	`conf`	Learning Augmented Binary Search Trees. ICML Honghao Lin, Tian Luo, David P. Woodruff
2022	J	`jnl`	Learning Augmented Binary Search Trees. CoRR Honghao Lin, Tian Luo, David P. Woodruff
2022	A*	`conf`	Learning-Augmented $k$-means Clustering. ICLR Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou
2022	A*	`conf`	Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time. ICML David P. Woodruff, Amir Zandieh
2022	J	`jnl`	Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time. CoRR David P. Woodruff, Amir Zandieh
2022	J	`jnl`	Low Rank Approximation for General Tensor Networks. CoRR Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang
2022	J	`jnl`	Low-Rank Approximation with 1/ε CoRR Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff
2022	A*	`conf`	Low-rank approximation with STOC Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff
2022	J	`jnl`	Memory Bounds for the Experts Problem. CoRR Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou
2022	A*	`conf`	Memory bounds for the experts problem. STOC Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou
2022	J	`jnl`	Near-Linear Sample Complexity for L CoRR Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou
2022	A*	`conf`	Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. SODA Nadiia Chepurko, Kenneth L. Clarkson, Praneeth Kacham, David P. Woodruff
2022	A	`conf`	Noisy Boolean Hidden Matching with Applications. ITCS Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou
2022	J	`jnl`	Online Lewis Weight Sampling. CoRR David P. Woodruff, Taisuke Yasuda
2022	J	`jnl`	Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. CoRR Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou
2022	A*	`conf`	Optimal Query Complexities for Dynamic Trace Estimation. NeurIPS David P. Woodruff, Fred Zhang, Richard Zhang
2022	J	`jnl`	Optimal Query Complexities for Dynamic Trace Estimation. CoRR David P. Woodruff, Fred Zhang, Qiuyi Zhang
2022	A*	`conf`	Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra. ICML Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin, David P. Woodruff
2022	J	`jnl`	Recovery from Non-Decomposable Distance Oracles. CoRR Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang
2022	A*	`conf`	Sketching Algorithms and Lower Bounds for Ridge Regression. ICML Praneeth Kacham, David P. Woodruff
2022	J	`jnl`	Sketching Algorithms and Lower Bounds for Ridge Regression. CoRR Praneeth Kacham, David P. Woodruff
2022	A	`conf`	Streaming Algorithms with Large Approximation Factors. APPROX/RANDOM Yi Li, Honghao Lin, David P. Woodruff, Yuheng Zhang
2022	J	`jnl`	Streaming Algorithms with Large Approximation Factors. CoRR Yi Li, Honghao Lin, David P. Woodruff, Yuheng Zhang
2022	J	`jnl`	Technical Perspective: Model Counting Meets Distinct Elements in a Data Stream. SIGMOD Rec. David P. Woodruff
2022	A*	`conf`	Testing Positive Semidefiniteness Using Linear Measurements. FOCS Deanna Needell, William Swartworth, David P. Woodruff
2022	J	`jnl`	Testing Positive Semidefiniteness Using Linear Measurements. CoRR Deanna Needell, William Swartworth, David P. Woodruff
2022	A*	`conf`	The White-Box Adversarial Data Stream Model. PODS Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou
2022	J	`jnl`	The White-Box Adversarial Data Stream Model. CoRR Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou
2022	J	`jnl`	The 𝓁 CoRR Yi Li, Honghao Lin, David P. Woodruff
2022	J	`jnl`	Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. CoRR Yi Li, David P. Woodruff
2022	J	`jnl`	Tight Bounds for ℓ ACM Trans. Algorithms Ruosong Wang, David P. Woodruff
2022	A*	`conf`	Triangle and Four Cycle Counting with Predictions in Graph Streams. ICLR Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang
2022	J	`jnl`	Triangle and Four Cycle Counting with Predictions in Graph Streams. CoRR Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang
2022	A*	`conf`	Truly Perfect Samplers for Data Streams and Sliding Windows. PODS Rajesh Jayaram, David P. Woodruff, Samson Zhou
2021	J	`jnl`	A Framework for Adversarially Robust Streaming Algorithms. SIGMOD Rec. Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev
2021	A	`conf`	A Simple Proof of a New Set Disjointness with Applications to Data Streams. CCC Akshay Kamath, Eric Price, David P. Woodruff
2021	J	`jnl`	A Simple Proof of a New Set Disjointness with Applications to Data Streams. CoRR Akshay Kamath, Eric Price, David P. Woodruff
2021	A*	`conf`	A Very Sketchy Talk (Invited Talk). ICALP David P. Woodruff
2021	J	`jnl`	Active Sampling for Linear Regression Beyond the $\ell_2$ Norm. CoRR Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda
2021	J	`jnl`	An Efficient Semi-Streaming PTAS for Tournament Feedback ArcSet with Few Passes. CoRR Anubhav Baweja, Justin Jia, David P. Woodruff
2021	A*	`conf`	Average-Case Communication Complexity of Statistical Problems. COLT Cyrus Rashtchian, David P. Woodruff, Peng Ye, Hanlin Zhu
2021	J	`jnl`	Average-Case Communication Complexity of Statistical Problems. CoRR Cyrus Rashtchian, David P. Woodruff, Peng Ye, Hanlin Zhu
2021	A*	`conf`	Dimensionality Reduction for the Sum-of-Distances Metric. ICML Zhili Feng, Praneeth Kacham, David P. Woodruff
2021	A*	`conf`	Exponentially Improved Dimensionality Reduction for l1: Subspace Embeddings and Independence Testing. COLT Yi Li, David P. Woodruff, Taisuke Yasuda
2021	J	`jnl`	Exponentially Improved Dimensionality Reduction for 𝓁 CoRR Yi Li, David P. Woodruff, Taisuke Yasuda
2021	A*	`conf`	Fast Sketching of Polynomial Kernels of Polynomial Degree. ICML Zhao Song, David P. Woodruff, Zheng Yu, Lichen Zhang
2021	J	`jnl`	Fast Sketching of Polynomial Kernels of Polynomial Degree. CoRR Zhao Song, David P. Woodruff, Zheng Yu, Lichen Zhang
2021	A*	`conf`	Few-Shot Data-Driven Algorithms for Low Rank Approximation. NeurIPS Piotr Indyk, Tal Wagner, David P. Woodruff
2021	J	`jnl`	Frequency Estimation with One-Sided Error. CoRR Piotr Indyk, Shyam Narayanan, David P. Woodruff
2021	J	`jnl`	How to Reduce Dimension With PCA and Random Projections? IEEE Trans. Inf. Theory Fan Yang, Sifan Liu, Edgar Dobriban, David P. Woodruff
2021	—	`conf`	Hutch++: Optimal Stochastic Trace Estimation. SOSA Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff
2021	J	`jnl`	ICALP 2022 - 49th EATCS International Colloquium on Automata, Languages and Programming. Bull. EATCS David P. Woodruff, Mikolaj Bojanczyk
2021	J	`jnl`	Improved Algorithms for Low Rank Approximation from Sparsity. CoRR David P. Woodruff, Taisuke Yasuda
2021	A*	`conf`	In-Database Regression in Input Sparsity Time. ICML Rajesh Jayaram, Alireza Samadian, David P. Woodruff, Peng Ye
2021	J	`jnl`	In-Database Regression in Input Sparsity Time. CoRR Rajesh Jayaram, Alireza Samadian, David P. Woodruff, Peng Ye
2021	A*	`conf`	Learning a Latent Simplex in Input Sparsity Time. ICLR Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou
2021	J	`jnl`	Learning a Latent Simplex in Input-Sparsity Time. CoRR Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou
2021	J	`jnl`	Learning-Augmented Sketches for Hessians. CoRR Yi Li, Honghao Lin, David P. Woodruff
2021	J	`jnl`	Learning-Augmented k-means Clustering. CoRR Jon Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou
2021	A*	`conf`	Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters. NeurIPS Arvind V. Mahankali, David P. Woodruff
2021	J	`jnl`	Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. CoRR Nadiia Chepurko, Kenneth L. Clarkson, Praneeth Kacham, David P. Woodruff
2021	J	`jnl`	Noisy Boolean Hidden Matching with Applications. CoRR Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou
2021	J	`jnl`	Non-PSD Matrix Sketching with Applications to Regression and Optimization. CoRR Zhili Feng, Fred Roosta, David P. Woodruff
2021	A	`conf`	Non-PSD matrix sketching with applications to regression and optimization. UAI Zhili Feng, Fred Roosta, David P. Woodruff
2021	A*	`conf`	Oblivious Sketching for Logistic Regression. ICML Alexander Munteanu, Simon Omlor, David P. Woodruff
2021	J	`jnl`	Oblivious sketching for logistic regression. CoRR Alexander Munteanu, Simon Omlor, David P. Woodruff
2021	A*	`conf`	Optimal SODA Arvind V. Mahankali, David P. Woodruff
2021	A*	`conf`	Optimal Sketching for Trace Estimation. NeurIPS Shuli Jiang, Hai Pham, David P. Woodruff, Qiuyi (Richard) Zhang
2021	J	`jnl`	Optimal Sketching for Trace Estimation. CoRR Shuli Jiang, Hai Pham, David P. Woodruff, Qiuyi (Richard) Zhang
2021	J	`jnl`	Perfect L SIAM J. Comput. Rajesh Jayaram, David P. Woodruff
2021	J	`jnl`	Querying a Matrix through Matrix-Vector Products. ACM Trans. Algorithms Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang
2021	A*	`conf`	Reduced-Rank Regression with Operator Norm Error. COLT Praneeth Kacham, David P. Woodruff
2021	A*	`conf`	Separations for Estimating Large Frequency Moments on Data Streams. ICALP David P. Woodruff, Samson Zhou
2021	J	`jnl`	Separations for Estimating Large Frequency Moments on Data Streams. CoRR David P. Woodruff, Samson Zhou
2021	A	`conf`	Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation. ITCS Cameron Musco, Christopher Musco, David P. Woodruff
2021	A*	`conf`	Single Pass Entrywise-Transformed Low Rank Approximation. ICML Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David P. Woodruff
2021	J	`jnl`	Single Pass Entrywise-Transformed Low Rank Approximation. CoRR Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David P. Woodruff
2021	A*	`conf`	Streaming and Distributed Algorithms for Robust Column Subset Selection. ICML Shuli Jiang, Dennis Li, Irene Mengze Li, Arvind V. Mahankali, David P. Woodruff
2021	J	`jnl`	Streaming and Distributed Algorithms for Robust Column Subset Selection. CoRR Shuli Jiang, Dongyu Li, Irene Mengze Li, Arvind V. Mahankali, David P. Woodruff
2021	A*	`conf`	Subspace Exploration: Bounds on Projected Frequency Estimation. PODS Graham Cormode, Charlie Dickens, David P. Woodruff
2021	J	`jnl`	Subspace exploration: Bounds on Projected Frequency Estimation. CoRR Graham Cormode, Charlie Dickens, David P. Woodruff
2021	—	`conf`	The Product of Gaussian Matrices Is Close to Gaussian. APPROX-RANDOM Yi Li, David P. Woodruff
2021	J	`jnl`	The Product of Gaussian Matrices is Close to Gaussian. CoRR Yi Li, David P. Woodruff
2021	A*	`conf`	Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. FOCS David P. Woodruff, Samson Zhou
2021	J	`jnl`	Tight Bounds for the Subspace Sketch Problem with Applications. SIAM J. Comput. Yi Li, Ruosong Wang, David P. Woodruff
2021	J	`jnl`	Truly Perfect Samplers for Data Streams and Sliding Windows. CoRR Rajesh Jayaram, David P. Woodruff, Samson Zhou
2021	J	`jnl`	Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020. CoRR Shuchi Chawla, Jelani Nelson, Chris Umans, David P. Woodruff
2020	A*	`conf`	A Framework for Adversarially Robust Streaming Algorithms. PODS Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev
2020	J	`jnl`	A Framework for Adversarially Robust Streaming Algorithms. CoRR Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev
2020	J	`jnl`	Approximation Algorithms for Sparse Principal Component Analysis. CoRR Agniva Chowdhury, Petros Drineas, David P. Woodruff, Samson Zhou
2020	A	`conf`	Automatic Differentiation of Sketched Regression. AISTATS Hang Liao, Barak A. Pearlmutter, Vamsi K. Potluru, David P. Woodruff
2020	J	`jnl`	Average Case Column Subset Selection for Entrywise 𝓁 CoRR Zhao Song, David P. Woodruff, Peilin Zhong
2020	A	`conf`	Graph Spanners in the Message-Passing Model. ITCS Manuel Fernandez, David P. Woodruff, Taisuke Yasuda
2020	J	`jnl`	Hutch++: Optimal Stochastic Trace Estimation. CoRR Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff
2020	A*	`conf`	Input-Sparsity Low Rank Approximation in Schatten Norm. ICML Yi Li, David P. Woodruff
2020	J	`jnl`	Input-Sparsity Low Rank Approximation in Schatten Norm. CoRR Yi Li, David P. Woodruff
2020	J	`jnl`	Introduction to the Special Issue on SODA'18. ACM Trans. Algorithms Yin Tat Lee, Marcin Pilipczuk, David P. Woodruff
2020	A*	`conf`	LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew. WWW Cyrus Rashtchian, Aneesh Sharma, David P. Woodruff
2020	J	`jnl`	LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew. CoRR Cyrus Rashtchian, Aneesh Sharma, David P. Woodruff
2020	A*	`conf`	Learning-Augmented Data Stream Algorithms. ICLR Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, David P. Woodruff
2020	A*	`conf`	Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling. ICML David P. Woodruff, Amir Zandieh
2020	J	`jnl`	Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling. CoRR David P. Woodruff, Amir Zandieh
2020	A*	`conf`	Near Optimal Linear Algebra in the Online and Sliding Window Models. FOCS Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou
2020	J	`jnl`	Non-Adaptive Adaptive Sampling on Turnstile Streams. CoRR Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou
2020	A*	`conf`	Non-adaptive adaptive sampling on turnstile streams. STOC Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou
2020	A*	`conf`	Oblivious Sketching of High-Degree Polynomial Kernels. SODA Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh
2020	J	`jnl`	On Learned Sketches for Randomized Numerical Linear Algebra. CoRR Simin Liu, Tianrui Liu, Ali Vakilian, Yulin Wan, David P. Woodruff
2020	A*	`conf`	Optimal Communication-Distortion Tradeoff in Voting. EC Debmalya Mandal, Nisarg Shah, David P. Woodruff
2020	A	`conf`	Optimal Deterministic Coresets for Ridge Regression. AISTATS Praneeth Kacham, David P. Woodruff
2020	J	`jnl`	Optimal 𝓁 CoRR Arvind V. Mahankali, David P. Woodruff
2020	A	`conf`	Pseudo-Deterministic Streaming. ITCS Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff
2020	J	`jnl`	Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra. CoRR Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, David P. Woodruff
2020	J	`jnl`	Reduced-Rank Regression with Operator Norm Error. CoRR Praneeth Kacham, David P. Woodruff
2020	A*	`conf`	Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes. NeurIPS Quang Minh Hoang, Nghia Hoang, Hai Pham, David P. Woodruff
2020	J	`jnl`	Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes. CoRR Quang Minh Hoang, Trong Nghia Hoang, Hai Pham, David P. Woodruff
2020	A*	`conf`	Robust and Sample Optimal Algorithms for PSD Low Rank Approximation. FOCS Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff
2020	A*	`conf`	Span Recovery for Deep Neural Networks with Applications to Input Obfuscation. ICLR Rajesh Jayaram, David P. Woodruff, Qiuyi Zhang
2020	J	`jnl`	Span Recovery for Deep Neural Networks with Applications to Input Obfuscation. CoRR Rajesh Jayaram, David P. Woodruff, Qiuyi Zhang
2020	—	`conf`	Streaming Complexity of SVMs. APPROX-RANDOM Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff
2020	J	`jnl`	Streaming Complexity of SVMs. CoRR Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff
2020	A*	`conf`	The Coin Problem with Applications to Data Streams. FOCS Mark Braverman, Sumegha Garg, David P. Woodruff
2020	J	`jnl`	The Coin Problem with Applications to Data Streams. Electron. Colloquium Comput. Complex. Mark Braverman, Sumegha Garg, David P. Woodruff
2020	A*	`conf`	The Communication Complexity of Optimization. SODA Santosh S. Vempala, Ruosong Wang, David P. Woodruff
2020	J	`jnl`	Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. CoRR David P. Woodruff, Samson Zhou
2020	A*	`conf`	Tight Bounds for the Subspace Sketch Problem with Applications. SODA Yi Li, Ruosong Wang, David P. Woodruff
2020	—	`conf`	Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems. APPROX-RANDOM Cyrus Rashtchian, David P. Woodruff, Hanlin Zhu
2020	J	`jnl`	Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems. CoRR Cyrus Rashtchian, David P. Woodruff, Hanlin Zhu
2020	A*	`conf`	WOR and NeurIPS Edith Cohen, Rasmus Pagh, David P. Woodruff
2020	J	`jnl`	WOR and p's: Sketches for 𝓁 CoRR Edith Cohen, Rasmus Pagh, David P. Woodruff
2020	—	`conf`	Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. APPROX-RANDOM Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff
2019	A*	`conf`	A PTAS for ℓp-Low Rank Approximation. SODA Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff
2019	J	`jnl`	An Optimal Algorithm for ℓ ACM Trans. Algorithms Arnab Bhattacharyya, Palash Dey, David P. Woodruff
2019	A*	`conf`	Average Case Column Subset Selection for Entrywise 퓁 NeurIPS Zhao Song, David P. Woodruff, Peilin Zhong
2019	A	`conf`	Conditional Sparse $L_p$-norm Regression With Optimal Probability. AISTATS John Hainline, Brendan Juba, Hai S. Le, David P. Woodruff
2019	A*	`conf`	Dimensionality Reduction for Tukey Regression. ICML Kenneth L. Clarkson, Ruosong Wang, David P. Woodruff
2019	J	`jnl`	Dimensionality Reduction for Tukey Regression. CoRR Kenneth L. Clarkson, Ruosong Wang, David P. Woodruff
2019	A*	`conf`	Efficient and Thrifty Voting by Any Means Necessary. NeurIPS Debmalya Mandal, Ariel D. Procaccia, Nisarg Shah, David P. Woodruff
2019	A*	`conf`	Faster Algorithms for Binary Matrix Factorization. ICML Ravi Kumar, Rina Panigrahy, Ali Rahimi, David P. Woodruff
2019	A*	`conf`	Faster Algorithms for High-Dimensional Robust Covariance Estimation. COLT Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff
2019	J	`jnl`	Faster Algorithms for High-Dimensional Robust Covariance Estimation. CoRR Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff
2019	J	`jnl`	Graph Spanners in the Message-Passing Model. CoRR Manuel Fernandez, David P. Woodruff, Taisuke Yasuda
2019	A*	`conf`	Learning Two Layer Rectified Neural Networks in Polynomial Time. COLT Ainesh Bakshi, Rajesh Jayaram, David P. Woodruff
2019	J	`jnl`	Low-Rank Approximation from Communication Complexity. CoRR Cameron Musco, Christopher Musco, David P. Woodruff
2019	J	`jnl`	Non-Convex Matrix Completion and Related Problems via Strong Duality. J. Mach. Learn. Res. Maria-Florina Balcan, Yingyu Liang, Zhao Song, David P. Woodruff, Hongyang Zhang
2019	J	`jnl`	Oblivious Sketching of High-Degree Polynomial Kernels. CoRR Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh
2019	J	`jnl`	On Approximating Matrix Norms in Data Streams. SIAM J. Comput. Yi Li, Huy L. Nguyen, David P. Woodruff
2019	—	`conf`	On Coresets for Logistic Regression. GI-Jahrestagung Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff
2019	J	`jnl`	Optimal Random Sampling from Distributed Streams Revisited. CoRR Srikanta Tirthapura, David P. Woodruff
2019	A*	`conf`	Optimal Sketching for Kronecker Product Regression and Low Rank Approximation. NeurIPS Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, David P. Woodruff
2019	J	`jnl`	Optimal Sketching for Kronecker Product Regression and Low Rank Approximation. CoRR Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, David P. Woodruff
2019	J	`jnl`	Pseudo-deterministic Streaming. CoRR Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff
2019	J	`jnl`	Pseudo-deterministic Streaming. Electron. Colloquium Comput. Complex. Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff
2019	A*	`conf`	Querying a Matrix Through Matrix-Vector Products. ICALP Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang
2019	J	`jnl`	Querying a Matrix through Matrix-Vector Products. CoRR Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang
2019	A*	`conf`	Regularized Weighted Low Rank Approximation. NeurIPS Frank Ban, David P. Woodruff, Qiuyi (Richard) Zhang
2019	J	`jnl`	Regularized Weighted Low Rank Approximation. CoRR Frank Ban, David P. Woodruff, Qiuyi (Richard) Zhang
2019	A*	`conf`	Relative Error Tensor Low Rank Approximation. SODA Zhao Song, David P. Woodruff, Peilin Zhong
2019	A*	`conf`	Robust Communication-Optimal Distributed Clustering Algorithms. ICALP Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, David P. Woodruff
2019	J	`jnl`	Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation. CoRR Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff
2019	A*	`conf`	Sample-Optimal Low-Rank Approximation of Distance Matrices. COLT Piotr Indyk, Ali Vakilian, Tal Wagner, David P. Woodruff
2019	J	`jnl`	Sample-Optimal Low-Rank Approximation of Distance Matrices. CoRR Piotr Indyk, Ali Vakilian, Tal Wagner, David P. Woodruff
2019	A*	`conf`	Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams. ICALP David P. Woodruff, Guang Yang
2019	J	`jnl`	Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams. CoRR David P. Woodruff, Guang Yang
2019	B	`conf`	Sketching Algorithms for Genomic Data Analysis and Querying in a Secure Enclave. RECOMB Can Kockan, Kaiyuan Zhu, Natnatee Dokmai, Nikolai Karpov, M. Oguzhan Külekci, David P. Woodruff, Süleyman Cenk Sahinalp
2019	J	`jnl`	Strong Coresets for Subspace Approximation and k-Median in Nearly Linear Time. CoRR Zhili Feng, Praneeth Kacham, David P. Woodruff
2019	A*	`conf`	Sublinear Time Numerical Linear Algebra for Structured Matrices. AAAI Xiaofei Shi, David P. Woodruff
2019	J	`jnl`	Sublinear Time Numerical Linear Algebra for Structured Matrices. CoRR Xiaofei Shi, David P. Woodruff
2019	A*	`conf`	Testing Matrix Rank, Optimally. SODA Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang
2019	J	`jnl`	The Communication Complexity of Optimization. CoRR Santosh S. Vempala, Ruosong Wang, David P. Woodruff
2019	A*	`conf`	The One-Way Communication Complexity of Dynamic Time Warping Distance. SoCG Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang
2019	J	`jnl`	The One-Way Communication Complexity of Dynamic Time Warping Distance. CoRR Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang
2019	—	`conf`	The Query Complexity of Mastermind with l APPROX-RANDOM Manuel Fernandez, David P. Woodruff, Taisuke Yasuda
2019	J	`jnl`	The Query Complexity of Mastermind with 𝓁 CoRR Manuel Fernandez, David P. Woodruff, Taisuke Yasuda
2019	J	`jnl`	Tight Bounds for the Subspace Sketch Problem with Applications. CoRR Yi Li, Ruosong Wang, David P. Woodruff
2019	A*	`conf`	Tight Bounds for ℓp Oblivious Subspace Embeddings. SODA Ruosong Wang, David P. Woodruff
2019	A*	`conf`	Tight Dimensionality Reduction for Sketching Low Degree Polynomial Kernels. NeurIPS Michela Meister, Tamás Sarlós, David P. Woodruff
2019	A*	`conf`	Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-means Clustering. ICML Taisuke Yasuda, David P. Woodruff, Manuel Fernandez
2019	J	`jnl`	Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel k-means Clustering. CoRR Manuel Fernandez, David P. Woodruff, Taisuke Yasuda
2019	A*	`conf`	Total Least Squares Regression in Input Sparsity Time. NeurIPS Huaian Diao, Zhao Song, David P. Woodruff, Xin Yang
2019	J	`jnl`	Total Least Squares Regression in Input Sparsity Time. CoRR Huaian Diao, Zhao Song, David P. Woodruff, Xin Yang
2019	—	`conf`	Towards Optimal Moment Estimation in Streaming and Distributed Models. APPROX-RANDOM Rajesh Jayaram, David P. Woodruff
2019	J	`jnl`	Towards Optimal Moment Estimation in Streaming and Distributed Models. CoRR Rajesh Jayaram, David P. Woodruff
2019	A*	`conf`	Towards a Zero-One Law for Column Subset Selection. NeurIPS Zhao Song, David P. Woodruff, Peilin Zhong
2019	J	`jnl`	Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. CoRR Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff
2019	A*	`conf`	Weighted Reservoir Sampling from Distributed Streams. PODS Rajesh Jayaram, Gokarna Sharma, Srikanta Tirthapura, David P. Woodruff
2019	J	`jnl`	Weighted Reservoir Sampling from Distributed Streams. CoRR Rajesh Jayaram, Gokarna Sharma, Srikanta Tirthapura, David P. Woodruff
2018	J	`jnl`	A PTAS for 𝓁 CoRR Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff
2018	A*	`conf`	An Empirical Evaluation of Sketching for Numerical Linear Algebra. KDD Yogesh Dahiya, Dimitris Konomis, David P. Woodruff
2018	J	`jnl`	Conditional Sparse 𝓁 CoRR John Hainline, Brendan Juba, Hai S. Le, David P. Woodruff
2018	A*	`conf`	Data Streams with Bounded Deletions. PODS Rajesh Jayaram, David P. Woodruff
2018	J	`jnl`	Data Streams with Bounded Deletions. CoRR Rajesh Jayaram, David P. Woodruff
2018	A*	`conf`	Distributed Statistical Estimation of Matrix Products with Applications. PODS David P. Woodruff, Qin Zhang
2018	J	`jnl`	Distributed Statistical Estimation of Matrix Products with Applications. CoRR David P. Woodruff, Qin Zhang
2018	—	`ch.`	Frequency Moments. Encyclopedia of Database Systems (2nd ed.) David P. Woodruff
2018	A*	`conf`	High Probability Frequency Moment Sketches. ICALP Sumit Ganguly, David P. Woodruff
2018	J	`jnl`	High Probability Frequency Moment Sketches. CoRR Sumit Ganguly, David P. Woodruff
2018	A*	`conf`	Improved Algorithms for Adaptive Compressed Sensing. ICALP Vasileios Nakos, Xiaofei Shi, David P. Woodruff, Hongyang Zhang
2018	J	`jnl`	Improved Algorithms for Adaptive Compressed Sensing. CoRR Vasileios Nakos, Xiaofei Shi, David P. Woodruff, Hongyang Zhang
2018	J	`jnl`	Learning Two Layer Rectified Neural Networks in Polynomial Time. CoRR Ainesh Bakshi, Rajesh Jayaram, David P. Woodruff
2018	J	`jnl`	Leveraging Well-Conditioned Bases: Streaming \& Distributed Summaries in Minkowski p-Norms. CoRR Graham Cormode, Charlie Dickens, David P. Woodruff
2018	A*	`conf`	Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski p-Norms. ICML Graham Cormode, Charlie Dickens, David P. Woodruff
2018	A	`conf`	Matrix Completion and Related Problems via Strong Duality. ITCS Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, Hongyang Zhang
2018	A*	`conf`	Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order. ICML Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, Lin F. Yang
2018	J	`jnl`	Near Optimal Linear Algebra in the Online and Sliding Window Models CoRR Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou
2018	—	`conf`	Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. APPROX-RANDOM Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou
2018	J	`jnl`	Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. CoRR Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou
2018	A*	`conf`	On Coresets for Logistic Regression. NeurIPS Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff
2018	J	`jnl`	On Coresets for Logistic Regression. CoRR Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff
2018	—	`conf`	On Low-Risk Heavy Hitters and Sparse Recovery Schemes. APPROX-RANDOM Yi Li, Vasileios Nakos, David P. Woodruff
2018	—	`conf`	On Sketching the q to p Norms. APPROX-RANDOM Aditya Krishnan, Sidhanth Mohanty, David P. Woodruff
2018	J	`jnl`	On Sketching the q to p norms. CoRR Aditya Krishnan, Sidhanth Mohanty, David P. Woodruff
2018	J	`jnl`	Perfect L CoRR Rajesh Jayaram, David P. Woodruff
2018	A*	`conf`	Perfect Lp Sampling in a Data Stream. FOCS Rajesh Jayaram, David P. Woodruff
2018	J	`jnl`	Relative Error Tensor Low Rank Approximation. Electron. Colloquium Comput. Complex. Zhao Song, David P. Woodruff, Peilin Zhong
2018	A*	`conf`	Revisiting Frequency Moment Estimation in Random Order Streams. ICALP Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang
2018	J	`jnl`	Revisiting Frequency Moment Estimation in Random Order Streams. CoRR Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang
2018	A*	`conf`	Robust Subspace Approximation in a Stream. NeurIPS Roie Levin, Anish Prasad Sevekari, David P. Woodruff
2018	A	`conf`	Sketching for Kronecker Product Regression and P-splines. AISTATS Huaian Diao, Zhao Song, Wen Sun, David P. Woodruff
2018	A	`conf`	Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. ITCS Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff
2018	A*	`conf`	Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension. FOCS Christian Sohler, David P. Woodruff
2018	J	`jnl`	Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension. CoRR Christian Sohler, David P. Woodruff
2018	A*	`conf`	Sublinear Time Low-Rank Approximation of Distance Matrices. NeurIPS Ainesh Bakshi, David P. Woodruff
2018	J	`jnl`	Sublinear Time Low-Rank Approximation of Distance Matrices. CoRR Ainesh Bakshi, David P. Woodruff
2018	J	`jnl`	Testing Matrix Rank, Optimally. CoRR Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang
2018	J	`jnl`	Tight Bounds for 𝓁 CoRR Ruosong Wang, David P. Woodruff
2018	J	`jnl`	Towards a Zero-One Law for Entrywise Low Rank Approximation. CoRR Zhao Song, David P. Woodruff, Peilin Zhong
2017	A*	`conf`	Adaptive Matrix Vector Product. SODA Santosh S. Vempala, David P. Woodruff
2017	J	`jnl`	Algorithms for $\ell_p$ Low Rank Approximation. CoRR Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, David P. Woodruff
2017	A*	`conf`	Algorithms for $\ell_p$ Low-Rank Approximation. ICML Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, David P. Woodruff
2017	—	`conf`	Approximation Algorithms for l NIPS Karl Bringmann, Pavel Kolev, David P. Woodruff
2017	J	`jnl`	Approximation Algorithms for ࡁ CoRR Karl Bringmann, Pavel Kolev, David P. Woodruff
2017	A*	`conf`	BPTree: An ℓ PODS Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff
2017	J	`jnl`	Communication-Optimal Distributed Clustering. CoRR Jiecao Chen, He Sun, David P. Woodruff, Qin Zhang
2017	A*	`conf`	Embeddings of Schatten Norms with Applications to Data Streams. ICALP Yi Li, David P. Woodruff
2017	J	`jnl`	Embeddings of Schatten Norms with Applications to Data Streams. CoRR Yi Li, David P. Woodruff
2017	J	`jnl`	Fast Regression with an $\ell_\infty$ Guarantee. CoRR Eric Price, Zhao Song, David P. Woodruff
2017	A*	`conf`	Fast Regression with an $ell_infty$ Guarantee. ICALP Eric Price, Zhao Song, David P. Woodruff
2017	J	`jnl`	Faster Kernel Ridge Regression Using Sketching and Preconditioning. SIAM J. Matrix Anal. Appl. Haim Avron, Kenneth L. Clarkson, David P. Woodruff
2017	—	`conf`	Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? NIPS Cameron Musco, David P. Woodruff
2017	J	`jnl`	Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? CoRR Cameron Musco, David P. Woodruff
2017	A*	`conf`	Low rank approximation with entrywise l STOC Zhao Song, David P. Woodruff, Peilin Zhong
2017	A*	`conf`	Low-Rank PSD Approximation in Input-Sparsity Time. SODA Kenneth L. Clarkson, David P. Woodruff
2017	—	`conf`	Near Optimal Sketching of Low-Rank Tensor Regression. NIPS Xingguo Li, Jarvis D. Haupt, David P. Woodruff
2017	J	`jnl`	Near Optimal Sketching of Low-Rank Tensor Regression. CoRR Jarvis D. Haupt, Xingguo Li, David P. Woodruff
2017	J	`jnl`	On Low-Risk Heavy Hitters and Sparse Recovery Schemes. CoRR Yi Li, Vasileios Nakos, David P. Woodruff
2017	J	`jnl`	Optimal CUR Matrix Decompositions. SIAM J. Comput. Christos Boutsidis, David P. Woodruff
2017	A*	`conf`	Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams. FOCS Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh
2017	J	`jnl`	Optimal Sample Complexity for Matrix Completion and Related Problems via 𝓁s CoRR Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, Hongyang Zhang
2017	J	`jnl`	Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams. CoRR Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh
2017	J	`jnl`	Processing Big Data Streams (NII Shonan Meeting 2017-7). NII Shonan Meet. Rep. Vladimir Braverman, David P. Woodruff, Ke Yi
2017	J	`jnl`	Relative Error Tensor Low Rank Approximation. CoRR Zhao Song, David P. Woodruff, Peilin Zhong
2017	—	`conf`	Sharper Bounds for Regularized Data Fitting. APPROX-RANDOM Haim Avron, Kenneth L. Clarkson, David P. Woodruff
2017	A	`conf`	Sketching for Geometric Problems (Invited Talk). ESA David P. Woodruff
2017	J	`jnl`	Sketching for Kronecker Product Regression and P-splines. CoRR Huaian Diao, Zhao Song, Wen Sun, David P. Woodruff
2017	J	`jnl`	Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. CoRR Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff
2017	A*	`conf`	Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices. FOCS Cameron Musco, David P. Woodruff
2017	J	`jnl`	Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices. CoRR Cameron Musco, David P. Woodruff
2017	J	`jnl`	Theory and Applications of Hashing (Dagstuhl Seminar 17181). Dagstuhl Reports Martin Dietzfelbinger, Michael Mitzenmacher, Rasmus Pagh, David P. Woodruff, Martin Aumüller
2017	J	`jnl`	When distributed computation is communication expensive. Distributed Comput. David P. Woodruff, Qin Zhang
2016	J	`jnl`	A Simple Message-Optimal Algorithm for Random Sampling from a Distributed Stream. IEEE Trans. Knowl. Data Eng. Yung-Yu Chung, Srikanta Tirthapura, David P. Woodruff
2016	A*	`conf`	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems. PODS Arnab Bhattacharyya, Palash Dey, David P. Woodruff
2016	J	`jnl`	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems. CoRR Arnab Bhattacharyya, Palash Dey, David P. Woodruff
2016	J	`jnl`	BPTree: an ℓ CoRR Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff
2016	A*	`conf`	Beating CountSketch for heavy hitters in insertion streams. STOC Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff
2016	B	`conf`	Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond. SPAA Hossein Esfandiari, MohammadTaghi Hajiaghayi, David P. Woodruff
2016	J	`jnl`	Certifying Equality With Limited Interaction. Algorithmica Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev
2016	A*	`conf`	Communication Efficient Distributed Kernel Principal Component Analysis. KDD Maria-Florina Balcan, Yingyu Liang, Le Song, David P. Woodruff, Bo Xie
2016	A*	`conf`	Communication lower bounds for statistical estimation problems via a distributed data processing inequality. STOC Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff
2016	—	`conf`	Communication-Optimal Distributed Clustering. NIPS Jiecao Chen, He Sun, David P. Woodruff, Qin Zhang
2016	J	`jnl`	Distributed Low Rank Approximation of Implicit Functions of a Matrix. CoRR David P. Woodruff, Peilin Zhong
2016	A*	`conf`	Distributed low rank approximation of implicit functions of a matrix. ICDE David P. Woodruff, Peilin Zhong
2016	J	`jnl`	Editorial to the Special Issue on SODA'12. ACM Trans. Algorithms Yuval Rabani, Andréa W. Richa, Jared Saia, David P. Woodruff
2016	J	`jnl`	Faster Kernel Ridge Regression Using Sketching and Preconditioning. CoRR Haim Avron, Kenneth L. Clarkson, David P. Woodruff
2016	J	`jnl`	Frequent Directions: Simple and Deterministic Matrix Sketching. SIAM J. Comput. Mina Ghashami, Edo Liberty, Jeff M. Phillips, David P. Woodruff
2016	J	`jnl`	Guest Editorial for Information Complexity and Applications. Algorithmica Mark Braverman, David P. Woodruff
2016	A*	`conf`	How to Fake Multiply by a Gaussian Matrix. ICML Michael Kapralov, Vamsi K. Potluru, David P. Woodruff
2016	J	`jnl`	How to Fake Multiply by a Gaussian Matrix. CoRR Michael Kapralov, Vamsi K. Potluru, David P. Woodruff
2016	J	`jnl`	Low Rank Approximation with Entrywise ℓ CoRR Zhao Song, David P. Woodruff, Peilin Zhong
2016	A*	`conf`	Nearly-optimal bounds for sparse recovery in generic norms, with applications to SODA Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, David P. Woodruff
2016	A	`conf`	New Algorithms for Heavy Hitters in Data Streams (Invited Talk). ICDT David P. Woodruff
2016	J	`jnl`	New Algorithms for Heavy Hitters in Data Streams. CoRR David P. Woodruff
2016	A	`conf`	New Characterizations in Turnstile Streams with Applications. CCC Yuqing Ai, Wei Hu, Yi Li, David P. Woodruff
2016	J	`jnl`	On Approximating Functions of the Singular Values in a Stream. CoRR Yi Li, David P. Woodruff
2016	A	`conf`	On Sketching Quadratic Forms. ITCS Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang
2016	A*	`conf`	On approximating functions of the singular values in a stream. STOC Yi Li, David P. Woodruff
2016	A*	`conf`	Optimal Approximate Matrix Product in Terms of Stable Rank. ICALP Michael B. Cohen, Jelani Nelson, David P. Woodruff
2016	A*	`conf`	Optimal principal component analysis in distributed and streaming models. STOC Christos Boutsidis, David P. Woodruff, Peilin Zhong
2016	J	`jnl`	Recent Advances in Randomized Numerical Linear Algebra (NII Shonan Meeting 2016-10). NII Shonan Meet. Rep. Ravindran Kannan, Michael W. Mahoney, David P. Woodruff
2016	J	`jnl`	Sharper Bounds for Regression and Low-Rank Approximation with Regularization. CoRR Haim Avron, Kenneth L. Clarkson, David P. Woodruff
2016	J	`jnl`	Space-Efficient Estimation of Statistics Over Sub-Sampled Streams. Algorithmica Andrew McGregor, A. Pavan, Srikanta Tirthapura, David P. Woodruff
2016	A	`conf`	Stochastic Streams: Sample Complexity vs. Space Complexity. ESA Michael S. Crouch, Andrew McGregor, Gregory Valiant, David P. Woodruff
2016	A*	`conf`	Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors. PODS Vladimir Braverman, Stephen R. Chestnut, David P. Woodruff, Lin F. Yang
2016	J	`jnl`	Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors. CoRR Vladimir Braverman, Stephen R. Chestnut, David P. Woodruff, Lin F. Yang
2016	—	`conf`	Sublinear Time Orthogonal Tensor Decomposition. NIPS Zhao Song, David P. Woodruff, Huan Zhang
2016	J	`jnl`	The Fast Cauchy Transform and Faster Robust Linear Regression. SIAM J. Comput. Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff
2016	—	`conf`	Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. APPROX-RANDOM Yi Li, David P. Woodruff
2016	A*	`conf`	Weighted low rank approximations with provable guarantees. STOC Ilya P. Razenshteyn, Zhao Song, David P. Woodruff
2015	J	`jnl`	A General Method for Estimating Correlated Aggregates Over a Data Stream. Algorithmica Srikanta Tirthapura, David P. Woodruff
2015	—	`conf`	Amplification of One-Way Information Complexity via Codes and Noise Sensitivity. ICALP (1) Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev
2015	J	`jnl`	Amplification of One-Way Information Complexity via Codes and Noise Sensitivity. Electron. Colloquium Comput. Complex. Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev
2015	J	`jnl`	Applications of Uniform Sampling: Densest Subgraph and Beyond. CoRR Hossein Esfandiari, MohammadTaghi Hajiaghayi, David P. Woodruff
2015	J	`jnl`	Beating CountSketch for Heavy Hitters in Insertion Streams. CoRR Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff
2015	J	`jnl`	Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality. CoRR Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff
2015	J	`jnl`	Communication-optimal Distributed Principal Component Analysis in the Column-partition Model. CoRR Christos Boutsidis, David P. Woodruff
2015	J	`jnl`	Distributed Kernel Principal Component Analysis. CoRR Maria-Florina Balcan, Yingyu Liang, Le Song, David P. Woodruff, Bo Xie
2015	J	`jnl`	Frequent Directions : Simple and Deterministic Matrix Sketching. CoRR Mina Ghashami, Edo Liberty, Jeff M. Phillips, David P. Woodruff
2015	A*	`conf`	Input Sparsity and Hardness for Robust Subspace Approximation. FOCS Kenneth L. Clarkson, David P. Woodruff
2015	J	`jnl`	Input Sparsity and Hardness for Robust Subspace Approximation. CoRR Kenneth L. Clarkson, David P. Woodruff
2015	J	`jnl`	Nearly-optimal bounds for sparse recovery in generic norms, with applications to $k$-median sketching. CoRR Arturs Backurs, Piotr Indyk, Eric Price, Ilya P. Razenshteyn, David P. Woodruff
2015	J	`jnl`	On Sketching Quadratic Forms. CoRR Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang
2015	J	`jnl`	Optimal approximate matrix product in terms of stable rank. CoRR Michael B. Cohen, Jelani Nelson, David P. Woodruff
2015	A*	`conf`	Sketching for SODA Kenneth L. Clarkson, David P. Woodruff
2015	A*	`conf`	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication. PODS Dirk Van Gucht, Ryan Williams, David P. Woodruff, Qin Zhang
2015	—	`conf`	The Simultaneous Communication of Disjointness with Applications to Data Streams. ICALP (1) Omri Weinstein, David P. Woodruff
2015	J	`jnl`	The Simultaneous Communication of Disjointness with Applications to Data Streams. Electron. Colloquium Comput. Complex. Omri Weinstein, David P. Woodruff
2015	—	`conf`	Tight Bounds for Graph Problems in Insertion Streams. APPROX-RANDOM Xiaoming Sun, David P. Woodruff
2014	J	`jnl`	A Sketching Algorithm for Spectral Graph Sparsification. CoRR Jiecao Chen, Bo Qin, David P. Woodruff, Qin Zhang
2014	A*	`conf`	An Optimal Lower Bound for Distinct Elements in the Message Passing Model. SODA David P. Woodruff, Qin Zhang
2014	A*	`conf`	Beyond set disjointness: the communication complexity of finding the intersection. PODC Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev
2014	—	`conf`	Certifying Equality With Limited Interaction. APPROX-RANDOM Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev
2014	J	`jnl`	Data Streams and Applications in Computer Science. Bull. EATCS David P. Woodruff
2014	—	`conf`	Improved Distributed Principal Component Analysis. NIPS Yingyu Liang, Maria-Florina Balcan, Vandana Kanchanapally, David P. Woodruff
2014	J	`jnl`	Improved Distributed Principal Component Analysis. CoRR Maria-Florina Balcan, Vandana Kanchanapally, Yingyu Liang, David P. Woodruff
2014	A*	`conf`	Improved testing of low rank matrices. KDD Yi Li, Zhengyu Wang, David P. Woodruff
2014	A*	`conf`	Is min-wise hashing optimal for summarizing set intersection? PODS Rasmus Pagh, Morten Stöckel, David P. Woodruff
2014	—	`conf`	Low Rank Approximation Lower Bounds in Row-Update Streams. NIPS David P. Woodruff
2014	A*	`conf`	On Sketching Matrix Norms and the Top Singular Vector. SODA Yi Li, Huy L. Nguyen, David P. Woodruff
2014	J	`jnl`	On The Communication Complexity of Linear Algebraic Problems in the Message Passing Model. CoRR Yi Li, Xiaoming Sun, Chengu Wang, David P. Woodruff
2014	A	`conf`	On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model. DISC Yi Li, Xiaoming Sun, Chengu Wang, David P. Woodruff
2014	J	`jnl`	Optimal CUR Matrix Decompositions. CoRR Christos Boutsidis, David P. Woodruff
2014	A*	`conf`	Optimal CUR matrix decompositions. STOC Christos Boutsidis, David P. Woodruff
2014	A*	`conf`	Principal Component Analysis and Higher Correlations for Distributed Data. COLT Ravi Kannan, Santosh S. Vempala, David P. Woodruff
2014	J	`jnl`	Sketching as a Tool for Numerical Linear Algebra. CoRR David P. Woodruff
2014	J	`jnl`	Sketching as a Tool for Numerical Linear Algebra. Found. Trends Theor. Comput. Sci. David P. Woodruff
2014	A*	`conf`	Spanners and sparsifiers in dynamic streams. PODC Michael Kapralov, David P. Woodruff
2014	J	`jnl`	Steiner transitive-closure spanners of low-dimensional posets. Comb. Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
2014	—	`conf`	Subspace Embeddings for the Polynomial Kernel. NIPS Haim Avron, Huy L. Nguyen, David P. Woodruff
2014	J	`jnl`	The Sketching Complexity of Graph Cuts. CoRR Alexandr Andoni, Robert Krauthgamer, David P. Woodruff
2014	A*	`conf`	Turnstile streaming algorithms might as well be linear sketches. STOC Yi Li, Huy L. Nguyen, David P. Woodruff
2013	—	`conf`	A Tight Lower Bound for High Frequency Moment Estimation with Small Error. APPROX-RANDOM Yi Li, David P. Woodruff
2013	A*	`conf`	Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching. SODA Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev
2013	A*	`conf`	How robust are linear sketches to adaptive inputs? STOC Moritz Hardt, David P. Woodruff
2013	A*	`conf`	Low rank approximation and regression in input sparsity time. STOC Kenneth L. Clarkson, David P. Woodruff
2013	A*	`conf`	Lower Bounds for Adaptive Sparse Recovery. SODA Eric Price, David P. Woodruff
2013	J	`jnl`	Multi-Tuple Deletion Propagation: Approximations and Complexity. Proc. VLDB Endow. Benny Kimelfeld, Jan Vondrák, David P. Woodruff
2013	J	`jnl`	Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error. ACM Trans. Algorithms T. S. Jayram, David P. Woodruff
2013	—	`conf`	Sketching Structured Matrices for Faster Nonlinear Regression. NIPS Haim Avron, Vikas Sindhwani, David P. Woodruff
2013	A*	`conf`	Subspace Embeddings and $\ell_p$-Regression Using Exponential Random Variables. COLT David P. Woodruff, Qin Zhang
2013	J	`jnl`	Subspace Embeddings and ℓ CoRR David P. Woodruff, Qin Zhang
2013	A*	`conf`	The Fast Cauchy Transform and Faster Robust Linear Regression. SODA Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff
2013	A	`conf`	When Distributed Computation Is Communication Expensive. DISC David P. Woodruff, Qin Zhang
2013	J	`jnl`	When Distributed Computation does not Help CoRR David P. Woodruff, Qin Zhang
2012	A*	`conf`	A General Method for Estimating Correlated Aggregates over a Data Stream. ICDE Srikanta Tirthapura, David P. Woodruff
2012	J	`jnl`	A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. J. Comput. Sci. Technol. David P. Woodruff
2012	B	`conf`	Applications of the Shannon-Hartley theorem to data streams and sparse recovery. ISIT Eric Price, David P. Woodruff
2012	A*	`conf`	Fast approximation of matrix coherence and statistical leverage. ICML Michael W. Mahoney, Petros Drineas, Malik Magdon-Ismail, David P. Woodruff
2012	J	`jnl`	Fast approximation of matrix coherence and statistical leverage. J. Mach. Learn. Res. Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff
2012	J	`jnl`	How Robust are Linear Sketches to Adaptive Inputs? CoRR Moritz Hardt, David P. Woodruff
2012	J	`jnl`	Low Rank Approximation and Regression in Input Sparsity Time CoRR Kenneth L. Clarkson, David P. Woodruff
2012	J	`jnl`	Lower Bounds for Adaptive Sparse Recovery CoRR Eric Price, David P. Woodruff
2012	J	`jnl`	Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. SIAM J. Discret. Math. Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
2012	J	`jnl`	On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation CoRR Jelani Nelson, Huy L. Nguyên, David P. Woodruff
2012	—	`conf`	On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation. APPROX-RANDOM Jelani Nelson, Huy L. Nguyên, David P. Woodruff
2012	A*	`conf`	Rectangle-efficient aggregation in spatial data streams. PODS Srikanta Tirthapura, David P. Woodruff
2012	—	`conf`	Reusable low-error compressive sampling schemes through privacy. SSP Anna C. Gilbert, Brett Hemenway, Martin J. Strauss, David P. Woodruff, Mary Wootters
2012	A*	`conf`	Space-efficient estimation of statistics over sub-sampled streams. PODS Andrew McGregor, A. Pavan, Srikanta Tirthapura, David P. Woodruff
2012	J	`jnl`	Sublinear optimization for machine learning. J. ACM Kenneth L. Clarkson, Elad Hazan, David P. Woodruff
2012	J	`jnl`	The Fast Cauchy Transform: with Applications to Basis Construction, Regression, and Subspace Approximation in L1 CoRR Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff
2012	A*	`conf`	Tight bounds for distributed functional monitoring. STOC David P. Woodruff, Qin Zhang
2012	J	`jnl`	Transitive-Closure Spanners. SIAM J. Comput. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
2011	A*	`conf`	(1 + eps)-Approximate Sparse Recovery. FOCS Eric Price, David P. Woodruff
2011	J	`jnl`	(1+eps)-approximate Sparse Recovery CoRR Eric Price, David P. Woodruff
2011	J	`jnl`	Fast approximation of matrix coherence and statistical leverage CoRR Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff
2011	A*	`conf`	Fast moment estimation in data streams in optimal space. STOC Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff
2011	J	`jnl`	Lower Bounds for Sparse Recovery CoRR Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff
2011	A*	`conf`	Near-optimal private approximation protocols via a black box transformation. STOC David P. Woodruff
2011	J	`jnl`	On the Power of Adaptivity in Sparse Recovery CoRR Piotr Indyk, Eric Price, David P. Woodruff
2011	A*	`conf`	On the Power of Adaptivity in Sparse Recovery. FOCS Piotr Indyk, Eric Price, David P. Woodruff
2011	A*	`conf`	Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error. SODA T. S. Jayram, David P. Woodruff
2011	A	`conf`	Optimal Random Sampling from Distributed Streams Revisited. DISC Srikanta Tirthapura, David P. Woodruff
2011	—	`conf`	Steiner Transitive-Closure Spanners of Low-Dimensional Posets. ICALP (1) Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
2011	—	`conf`	Streaming Algorithms with One-Sided Estimation. APPROX-RANDOM Joshua Brody, David P. Woodruff
2011	A*	`conf`	Subspace embeddings for the L STOC Christian Sohler, David P. Woodruff
2011	A	`conf`	The Complexity of Linear Dependence Problems in Vector Spaces. ICS Arnab Bhattacharyya, Piotr Indyk, David P. Woodruff, Ning Xie
2011	J	`jnl`	Tight Bounds for Distributed Functional Monitoring CoRR David P. Woodruff, Qin Zhang
2011	A	`conf`	Tolerant Algorithms. ESA Rolf Klein, Rainer Penninger, Christian Sohler, David P. Woodruff
2010	A*	`conf`	1-Pass Relative-Error L SODA Morteza Monemizadeh, David P. Woodruff
2010	—	`conf`	A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. APPROX-RANDOM David P. Woodruff
2010	—	`conf`	Additive Spanners in Nearly Quadratic Time. ICALP (1) David P. Woodruff
2010	A*	`conf`	An optimal algorithm for the distinct elements problem. PODS Daniel M. Kane, Jelani Nelson, David P. Woodruff
2010	A*	`conf`	Coresets and Sketches for High Dimensional Subspace Approximation Problems. SODA Dan Feldman, Morteza Monemizadeh, Christian Sohler, David P. Woodruff
2010	J	`jnl`	Epistemic privacy. J. ACM Alexandre V. Evfimievski, Ronald Fagin, David P. Woodruff
2010	A*	`conf`	Fast Manhattan sketches in data streams. PODS Jelani Nelson, David P. Woodruff
2010	J	`jnl`	Fast Moment Estimation in Data Streams in Optimal Space CoRR Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff
2010	—	`conf`	Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. APPROX-RANDOM Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
2010	A*	`conf`	Lower Bounds for Sparse Recovery. SODA Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff
2010	A*	`conf`	On the Exact Space Complexity of Sketching and Streaming Small Norms. SODA Daniel M. Kane, Jelani Nelson, David P. Woodruff
2010	J	`jnl`	Steiner Transitive-Closure Spanners of d-Dimensional Posets CoRR Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
2010	J	`jnl`	Sublinear Optimization for Machine Learning CoRR Kenneth L. Clarkson, Elad Hazan, David P. Woodruff
2010	A*	`conf`	Sublinear Optimization for Machine Learning. FOCS Kenneth L. Clarkson, Elad Hazan, David P. Woodruff
2009	J	`jnl`	A Near-Optimal Algorithm for L1-Difference CoRR Jelani Nelson, David P. Woodruff
2009	A*	`conf`	Efficient Sketches for Earth-Mover Distance, with Applications. FOCS Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff
2009	—	`ch.`	Frequency Moments. Encyclopedia of Database Systems David P. Woodruff
2009	A*	`conf`	Numerical linear algebra in the streaming model. STOC Kenneth L. Clarkson, David P. Woodruff
2009	A*	`conf`	The Data Stream Space Complexity of Cascaded Norms. FOCS T. S. Jayram, David P. Woodruff
2009	A	`conf`	The average-case complexity of counting distinct elements. ICDT David P. Woodruff
2009	J	`jnl`	Transitive-Closure Spanners of the Hypercube and the Hypergrid. Electron. Colloquium Comput. Complex. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
2009	A*	`conf`	Transitive-closure spanners. SODA Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
2008	—	`conf`	Corruption and Recovery-Efficient Locally Decodable Codes. APPROX-RANDOM David P. Woodruff
2008	A*	`conf`	Epistemic privacy. PODS Alexandre V. Evfimievski, Ronald Fagin, David P. Woodruff
2008	J	`jnl`	Revisiting Norm Estimation in Data Streams CoRR Daniel M. Kane, Jelani Nelson, David P. Woodruff
2008	J	`jnl`	Transitive-Closure Spanners CoRR Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
2007	J	`jnl`	A Geometric Approach to Information-Theoretic Private Information Retrieval. SIAM J. Comput. David P. Woodruff, Sergey Yekhanin
2007	—	`—`	Efficient and private distance approximation in the communication and streaming models. David P. Woodruff
2007	J	`jnl`	New Lower Bounds for General Locally Decodable Codes. Electron. Colloquium Comput. Complex. David P. Woodruff
2007	A*	`conf`	Revisiting the Efficiency of Malicious Two-Party Computation. EUROCRYPT David P. Woodruff
2007	A*	`conf`	The communication and streaming complexity of computing the longest common and increasing subsequences. SODA Xiaoming Sun, David P. Woodruff
2006	—	`conf`	Better Approximations for the Minimum Common Integer Partition Problem. APPROX-RANDOM David P. Woodruff
2006	A*	`conf`	Explicit Exclusive Set Systems with Applications to Broadcast Encryption. FOCS Craig Gentry, Zulfikar Ramzan, David P. Woodruff
2006	A*	`conf`	Fast Algorithms for the Free Riders Problem in Broadcast Encryption. CRYPTO Zulfikar Ramzan, David P. Woodruff
2006	J	`jnl`	Fast Algorithms for the Free Riders Problem in Broadcast Encryption. IACR Cryptol. ePrint Arch. Zulfikar Ramzan, David P. Woodruff
2006	A*	`conf`	Lower Bounds for Additive Spanners, Emulators, and More. FOCS David P. Woodruff
2006	B	`conf`	Polylogarithmic Private Approximations and Efficient Matching. TCC Piotr Indyk, David P. Woodruff
2006	J	`jnl`	Revisiting the Efficiency of Malicious Two-Party Computation. IACR Cryptol. ePrint Arch. David P. Woodruff
2005	J	`jnl`	A Geometric Approach to Information-Theoretic Private Information Retrieval Electron. Colloquium Comput. Complex. David P. Woodruff, Sergey Yekhanin
2005	A	`conf`	A Geometric Approach to Information-Theoretic Private Information Retrieval. CCC David P. Woodruff, Sergey Yekhanin
2005	A*	`conf`	Optimal approximations of the frequency moments of data streams. STOC Piotr Indyk, David P. Woodruff
2005	J	`jnl`	Polylogarithmic Private Approximations and Efficient Matching Electron. Colloquium Comput. Complex. Piotr Indyk, David P. Woodruff
2005	A*	`conf`	Practical Cryptography in High Dimensional Tori. EUROCRYPT Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, David P. Woodruff
2004	A*	`conf`	Asymptotically Optimal Communication for Torus-Based Cryptography. CRYPTO Marten van Dijk, David P. Woodruff
2004	A*	`conf`	Clustering via Matrix Powering. PODS Hanson Zhou, David P. Woodruff
2004	A*	`conf`	Optimal space lower bounds for all frequency moments. SODA David P. Woodruff
2004	J	`jnl`	Practical Cryptography in High Dimensional Tori. IACR Cryptol. ePrint Arch. Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, David P. Woodruff
2004	J	`jnl`	Private Inference Control. IACR Cryptol. ePrint Arch. David P. Woodruff, Jessica Staddon
2004	A*	`conf`	Private inference control. CCS David P. Woodruff, Jessica Staddon
2003	A*	`conf`	Tight Lower Bounds for the Distinct Elements Problem. FOCS Piotr Indyk, David P. Woodruff
2002	A*	`conf`	Cryptography in an Unbounded Computational Model. EUROCRYPT David P. Woodruff, Marten van Dijk