David P. Woodruff

According to our database, David P. Woodruff authored at least 352 papers between 2002 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Streaming Algorithms with Few State Changes.

Rajesh Jayaram, David P. Woodruff, Samson Zhou

Proc. ACM Manag. Data, 2024

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut.

Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, Jason Zhang

Proc. ACM Manag. Data, 2024

A Strong Separation for Adversarially Robust ℓ₀ Estimation for Linear Sketches.

Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou

CoRR, 2024

Nearly Linear Sparsification of ℓ_p Subspace Approximation.

David P. Woodruff, Taisuke Yasuda

CoRR, 2024

Coresets for Multiple ℓ_p Regression.

David P. Woodruff, Taisuke Yasuda

CoRR, 2024

Optimal Communication for Classic Functions in the Coordinator Model and Beyond.

Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong

CoRR, 2024

Improving the Bit Complexity of Communication for Distributed Convex Optimization.

Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, Guanghao Ye

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond.

Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

A New Information Complexity Measure for Multi-pass Streaming with Applications.

Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Approximation Algorithms on Matrices - With Some Database Applications!

David P. Woodruff

Proceedings of the Companion of the 43rd Symposium on Principles of Database Systems, 2024

Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions.

Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions.

Justin Y. Chen, Piotr Indyk, David P. Woodruff

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra.

Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Coresets for Multiple ℓp Regression.

David P. Woodruff, Taisuke Yasuda

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Reweighted Solutions for Weighted Low Rank Approximation.

David P. Woodruff, Taisuke Yasuda

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Fast Sampling-Based Sketches for Tensors.

William J. Swartworth, David P. Woodruff

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Learning Multiple Secrets in Mastermind.

Milind Prabhu, David P. Woodruff

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Fast White-Box Adversarial Streaming Without a Random Oracle.

Ying Feng, Aayush Jain, David P. Woodruff

Proceedings of the Forty-first International Conference on Machine Learning, 2024

High-Dimensional Geometric Streaming for Nearly Low Rank Data.

Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond.

Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, Michael Wunder

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Adaptive Regret for Bandits Made Possible: Two Queries Suffice.

Zhou Lu, Qiuyi Zhang, Xinyi Chen, Fred Zhang, David P. Woodruff, Elad Hazan

Proceedings of the Twelfth International Conference on Learning Representations, 2024

HyperAttention: Long-context Attention in Near-Linear Time.

Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, Amir Zandieh

Proceedings of the Twelfth International Conference on Learning Representations, 2024

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms.

Yi Li, Honghao Lin, David P. Woodruff

Proceedings of the Twelfth International Conference on Learning Representations, 2024

GRASS: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients.

Aashiq Muhamed, Oscar Li, David P. Woodruff, Mona Diab, Virginia Smith

Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, 2024

Faster Algorithms for Schatten-p Low Rank Approximation.

Praneeth Kacham, David P. Woodruff

Proceedings of the Approximation, 2024

2023

Recovery From Non-Decomposable Distance Oracles.

Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang

IEEE Trans. Inf. Theory, October, 2023

Technical Perspective: Tapping the Link between Algorithmic Model Counting and Streaming.

David P. Woodruff

Commun. ACM, September, 2023

Towards Optimal Moment Estimation in Streaming and Distributed Models.

Rajesh Jayaram, David P. Woodruff

ACM Trans. Algorithms, July, 2023

On Differential Privacy and Adaptive Data Analysis with Bounded Space.

Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou

IACR Cryptol. ePrint Arch., 2023

Task-Based MoE for Multitask Multilingual Machine Translation.

Hai Pham, Young Jin Kim, Subhabrata Mukherjee, David P. Woodruff, Barnabás Póczos, Hany Hassan Awadalla

CoRR, 2023

Almost Linear Constant-Factor Sketching for 𝓁₁ and Logistic Regression.

Alexander Munteanu, Simon Omlor, David P. Woodruff

CoRR, 2023

Streaming Algorithms for Learning with Experts: Deterministic Versus Robust.

David P. Woodruff, Fred Zhang, Samson Zhou

CoRR, 2023

New Subset Selection Algorithms for Low Rank Approximation: Offline and Online.

David P. Woodruff, Taisuke Yasuda

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Optimal Eigenvalue Approximation via Sketching.

William Swartworth, David P. Woodruff

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Online Lewis Weight Sampling.

David P. Woodruff, Taisuke Yasuda

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Near-Linear Sample Complexity for <i>L_p</i> Polynomial Regression.

Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time.

Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

The ℓ_<i>p</i>-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines.

Yi Li, Honghao Lin, David P. Woodruff

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

On Robust Streaming for Learning with Experts: Algorithms and Lower Bounds.

David P. Woodruff, Fred Zhang, Samson Zhou

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Near-Optimal k-Clustering in the Sliding Window Model.

David P. Woodruff, Peilin Zhong, Samson Zhou

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products.

Tamás Sarlós, Xingyou Song, David P. Woodruff, Richard Zhang

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Computing Approximate 𝓁_p Sensitivities.

Swati Padmanabhan, David P. Woodruff, Richard Zhang

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Lower Bounds on Adaptive Sensing for Matrix Recovery.

Praneeth Kacham, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming.

Gregory Dexter, Petros Drineas, David P. Woodruff, Taisuke Yasuda

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Sharper Bounds for ℓ_p Sensitivity Sampling.

David P. Woodruff, Taisuke Yasuda

Proceedings of the International Conference on Machine Learning, 2023

Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization.

Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou

Proceedings of the International Conference on Machine Learning, 2023

Improved Algorithms for White-Box Adversarial Streams.

Ying Feng, David P. Woodruff

Proceedings of the International Conference on Machine Learning, 2023

Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression.

Alexander Munteanu, Simon Omlor, David P. Woodruff

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Robust Algorithms on Adaptive Inputs from Bounded Adversaries.

Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Learning the Positions in CountSketch.

Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David P. Woodruff

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming.

Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Streaming Euclidean k-median and k-means with o(log n) Space.

Vincent Cohen-Addad, David P. Woodruff, Samson Zhou

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

ℓ_p-Regression in the Arbitrary Partition Model of Communication.

Yi Li, Honghao Lin, David P. Woodruff

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Optimal Sketching Bounds for Sparse Linear Regression.

Tung Mai, Alexander Munteanu, Cameron Musco, Anup Rao, Chris Schwiegelshohn, David P. Woodruff

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2023

2022

Tight Bounds for ℓ₁ Oblivious Subspace Embeddings.

Ruosong Wang, David P. Woodruff

ACM Trans. Algorithms, 2022

Technical Perspective: Model Counting Meets Distinct Elements in a Data Stream.

David P. Woodruff

SIGMOD Rec., 2022

The 𝓁_p-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines.

Yi Li, Honghao Lin, David P. Woodruff

CoRR, 2022

Near-Linear Sample Complexity for L_p Polynomial Regression.

Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou

CoRR, 2022

Low Rank Approximation for General Tensor Networks.

Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang

CoRR, 2022

Low-Rank Approximation with 1/ε^1/3 Matrix-Vector Products.

Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff

CoRR, 2022

Memory bounds for the experts problem.

Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Low-rank approximation with <i>1/ε^1/3</i> matrix-vector products.

Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Improved Algorithms for Low Rank Approximation from Sparsity.

David P. Woodruff, Taisuke Yasuda

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Frequency Estimation with One-Sided Error.

Piotr Indyk, Shyam Narayanan, David P. Woodruff

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time.

Nadiia Chepurko, Kenneth L. Clarkson, Praneeth Kacham, David P. Woodruff

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World.

Agniva Chowdhury, Aritra Bose, Samson Zhou, David P. Woodruff, Petros Drineas

Proceedings of the Research in Computational Molecular Biology, 2022

Truly Perfect Samplers for Data Streams and Sliding Windows.

Rajesh Jayaram, David P. Woodruff, Samson Zhou

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

The White-Box Adversarial Data Stream Model.

Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Optimal Query Complexities for Dynamic Trace Estimation.

David P. Woodruff, Fred Zhang, Richard Zhang

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Noisy Boolean Hidden Matching with Applications.

Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes.

Anubhav Baweja, Justin Jia, David P. Woodruff

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time.

David P. Woodruff, Amir Zandieh

Proceedings of the International Conference on Machine Learning, 2022

Bounding the Width of Neural Networks via Coupled Initialization A Worst Case Analysis.

Alexander Munteanu, Simon Omlor, Zhao Song, David P. Woodruff

Proceedings of the International Conference on Machine Learning, 2022

Learning Augmented Binary Search Trees.

Honghao Lin, Tian Luo, David P. Woodruff

Proceedings of the International Conference on Machine Learning, 2022

Sketching Algorithms and Lower Bounds for Ridge Regression.

Praneeth Kacham, David P. Woodruff

Proceedings of the International Conference on Machine Learning, 2022

Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra.

Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin, David P. Woodruff

Proceedings of the International Conference on Machine Learning, 2022

Fast Regression for Structured Inputs.

Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou

Proceedings of the Tenth International Conference on Learning Representations, 2022

Learning-Augmented $k$-means Clustering.

Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou

Proceedings of the Tenth International Conference on Learning Representations, 2022

Triangle and Four Cycle Counting with Predictions in Graph Streams.

Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang

Proceedings of the Tenth International Conference on Learning Representations, 2022

High-Dimensional Geometric Streaming in Polynomial Space.

David P. Woodruff, Taisuke Yasuda

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Testing Positive Semidefiniteness Using Linear Measurements.

Deanna Needell, William Swartworth, David P. Woodruff

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Active Linear Regression for ℓp Norms and Beyond.

Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Adaptive Sketches for Robust Regression with Importance Sampling.

Sepideh Mahabadi, David P. Woodruff, Samson Zhou

Proceedings of the Approximation, 2022

Streaming Algorithms with Large Approximation Factors.

Yi Li, Honghao Lin, David P. Woodruff, Yuheng Zhang

Proceedings of the Approximation, 2022

2021

How to Reduce Dimension With PCA and Random Projections?

Fan Yang, Sifan Liu, Edgar Dobriban, David P. Woodruff

IEEE Trans. Inf. Theory, 2021

Querying a Matrix through Matrix-Vector Products.

Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang

ACM Trans. Algorithms, 2021

A Framework for Adversarially Robust Streaming Algorithms.

Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev

SIGMOD Rec., 2021

Tight Bounds for the Subspace Sketch Problem with Applications.

Yi Li, Ruosong Wang, David P. Woodruff

SIAM J. Comput., 2021

Perfect L_p Sampling in a Data Stream.

Rajesh Jayaram, David P. Woodruff

SIAM J. Comput., 2021

ICALP 2022 - 49th EATCS International Colloquium on Automata, Languages and Programming.

David P. Woodruff, Mikolaj Bojanczyk

Bull. EATCS, 2021

Active Sampling for Linear Regression Beyond the $\ell_2$ Norm.

Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda

CoRR, 2021

Streaming and Distributed Algorithms for Robust Column Subset Selection.

Shuli Jiang, Dongyu Li, Irene Mengze Li, Arvind V. Mahankali, David P. Woodruff

CoRR, 2021

An Efficient Semi-Streaming PTAS for Tournament Feedback ArcSet with Few Passes.

Anubhav Baweja, Justin Jia, David P. Woodruff

CoRR, 2021

Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020.

Shuchi Chawla, Jelani Nelson, Chris Umans, David P. Woodruff

CoRR, 2021

Exponentially Improved Dimensionality Reduction for 𝓁₁: Subspace Embeddings and Independence Testing.

Yi Li, David P. Woodruff, Taisuke Yasuda

CoRR, 2021

Learning-Augmented Sketches for Hessians.

Yi Li, Honghao Lin, David P. Woodruff

CoRR, 2021

Non-PSD matrix sketching with applications to regression and optimization.

Zhili Feng, Fred Roosta, David P. Woodruff

Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, 2021

Hutch++: Optimal Stochastic Trace Estimation.

Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Optimal <i>ℓ</i>₁ Column Subset Selection and a Fast PTAS for Low Rank Approximation.

Arvind V. Mahankali, David P. Woodruff

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Subspace Exploration: Bounds on Projected Frequency Estimation.

Graham Cormode, Charlie Dickens, David P. Woodruff

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters.

Arvind V. Mahankali, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Optimal Sketching for Trace Estimation.

Shuli Jiang, Hai Pham, David P. Woodruff, Qiuyi (Richard) Zhang

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Few-Shot Data-Driven Algorithms for Low Rank Approximation.

Piotr Indyk, Tal Wagner, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation.

Cameron Musco, Christopher Musco, David P. Woodruff

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Oblivious Sketching for Logistic Regression.

Alexander Munteanu, Simon Omlor, David P. Woodruff

Proceedings of the 38th International Conference on Machine Learning, 2021

Single Pass Entrywise-Transformed Low Rank Approximation.

Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David P. Woodruff

Proceedings of the 38th International Conference on Machine Learning, 2021

Streaming and Distributed Algorithms for Robust Column Subset Selection.

Shuli Jiang, Dennis Li, Irene Mengze Li, Arvind V. Mahankali, David P. Woodruff

Proceedings of the 38th International Conference on Machine Learning, 2021

In-Database Regression in Input Sparsity Time.

Rajesh Jayaram, Alireza Samadian, David P. Woodruff, Peng Ye

Proceedings of the 38th International Conference on Machine Learning, 2021

Dimensionality Reduction for the Sum-of-Distances Metric.

Zhili Feng, Praneeth Kacham, David P. Woodruff

Proceedings of the 38th International Conference on Machine Learning, 2021

Fast Sketching of Polynomial Kernels of Polynomial Degree.

Zhao Song, David P. Woodruff, Zheng Yu, Lichen Zhang

Proceedings of the 38th International Conference on Machine Learning, 2021

Learning a Latent Simplex in Input Sparsity Time.

Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou

Proceedings of the 9th International Conference on Learning Representations, 2021

Separations for Estimating Large Frequency Moments on Data Streams.

David P. Woodruff, Samson Zhou

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

A Very Sketchy Talk (Invited Talk).

David P. Woodruff

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators.

David P. Woodruff, Samson Zhou

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Average-Case Communication Complexity of Statistical Problems.

Cyrus Rashtchian, David P. Woodruff, Peng Ye, Hanlin Zhu

Proceedings of the Conference on Learning Theory, 2021

Exponentially Improved Dimensionality Reduction for l1: Subspace Embeddings and Independence Testing.

Yi Li, David P. Woodruff, Taisuke Yasuda

Proceedings of the Conference on Learning Theory, 2021

Reduced-Rank Regression with Operator Norm Error.

Praneeth Kacham, David P. Woodruff

Proceedings of the Conference on Learning Theory, 2021

A Simple Proof of a New Set Disjointness with Applications to Data Streams.

Akshay Kamath, Eric Price, David P. Woodruff

Proceedings of the 36th Computational Complexity Conference, 2021

The Product of Gaussian Matrices Is Close to Gaussian.

Yi Li, David P. Woodruff

Proceedings of the Approximation, 2021

2020

Introduction to the Special Issue on SODA'18.

Yin Tat Lee, Marcin Pilipczuk, David P. Woodruff

ACM Trans. Algorithms, 2020

The Coin Problem with Applications to Data Streams.

Mark Braverman, Sumegha Garg, David P. Woodruff

Electron. Colloquium Comput. Complex., 2020

Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes.

Quang Minh Hoang, Trong Nghia Hoang, Hai Pham, David P. Woodruff

CoRR, 2020

Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra.

Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, David P. Woodruff

CoRR, 2020

Optimal 𝓁₁ Column Subset Selection and a Fast PTAS for Low Rank Approximation.

Arvind V. Mahankali, David P. Woodruff

CoRR, 2020

On Learned Sketches for Randomized Numerical Linear Algebra.

Simin Liu, Tianrui Liu, Ali Vakilian, Yulin Wan, David P. Woodruff

CoRR, 2020

WOR and p's: Sketches for 𝓁_p-Sampling Without Replacement.

Edith Cohen, Rasmus Pagh, David P. Woodruff

CoRR, 2020

Approximation Algorithms for Sparse Principal Component Analysis.

Agniva Chowdhury, Petros Drineas, David P. Woodruff, Samson Zhou

CoRR, 2020

Average Case Column Subset Selection for Entrywise 𝓁₁-Norm Loss.

Zhao Song, David P. Woodruff, Peilin Zhong

CoRR, 2020

LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew.

Cyrus Rashtchian, Aneesh Sharma, David P. Woodruff

Proceedings of the WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, 2020

Non-adaptive adaptive sampling on turnstile streams.

Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

The Communication Complexity of Optimization.

Santosh S. Vempala, Ruosong Wang, David P. Woodruff

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Oblivious Sketching of High-Degree Polynomial Kernels.

Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Optimal Communication-Distortion Tradeoff in Voting.

Debmalya Mandal, Nisarg Shah, David P. Woodruff

Proceedings of the EC '20: The 21st ACM Conference on Economics and Computation, 2020

Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes.

Quang Minh Hoang, Nghia Hoang, Hai Pham, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

WOR and <i>p</i>'s: Sketches for ℓ_p-Sampling Without Replacement.

Edith Cohen, Rasmus Pagh, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Graph Spanners in the Message-Passing Model.

Manuel Fernandez, David P. Woodruff, Taisuke Yasuda

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling.

David P. Woodruff, Amir Zandieh

Proceedings of the 37th International Conference on Machine Learning, 2020

Input-Sparsity Low Rank Approximation in Schatten Norm.

Yi Li, David P. Woodruff

Proceedings of the 37th International Conference on Machine Learning, 2020

Learning-Augmented Data Stream Algorithms.

Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, David P. Woodruff

Proceedings of the 8th International Conference on Learning Representations, 2020

Span Recovery for Deep Neural Networks with Applications to Input Obfuscation.

Rajesh Jayaram, David P. Woodruff, Qiuyi Zhang

Proceedings of the 8th International Conference on Learning Representations, 2020

Near Optimal Linear Algebra in the Online and Sliding Window Models.

Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Robust and Sample Optimal Algorithms for PSD Low Rank Approximation.

Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems.

Cyrus Rashtchian, David P. Woodruff, Hanlin Zhu

Proceedings of the Approximation, 2020

Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.

Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff

Proceedings of the Approximation, 2020

Streaming Complexity of SVMs.

Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff

Proceedings of the Approximation, 2020

Automatic Differentiation of Sketched Regression.

Hang Liao, Barak A. Pearlmutter, Vamsi K. Potluru, David P. Woodruff

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

Optimal Deterministic Coresets for Ridge Regression.

Praneeth Kacham, David P. Woodruff

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

An Optimal Algorithm for ℓ₁-Heavy Hitters in Insertion Streams and Related Problems.

Arnab Bhattacharyya, Palash Dey, David P. Woodruff

ACM Trans. Algorithms, 2019

On Approximating Matrix Norms in Data Streams.

Yi Li, Huy L. Nguyen, David P. Woodruff

SIAM J. Comput., 2019

Non-Convex Matrix Completion and Related Problems via Strong Duality.

Maria-Florina Balcan, Yingyu Liang, Zhao Song, David P. Woodruff, Hongyang Zhang

J. Mach. Learn. Res., 2019

Pseudo-deterministic Streaming.

Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff

Electron. Colloquium Comput. Complex., 2019

Strong Coresets for Subspace Approximation and k-Median in Nearly Linear Time.

Zhili Feng, Praneeth Kacham, David P. Woodruff

CoRR, 2019

Oblivious Sketching of High-Degree Polynomial Kernels.

Michael Kapralov, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh

CoRR, 2019

Low-Rank Approximation from Communication Complexity.

Cameron Musco, Christopher Musco, David P. Woodruff

CoRR, 2019

Tight Bounds for ℓp Oblivious Subspace Embeddings.

Ruosong Wang, David P. Woodruff

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A PTAS for ℓp-Low Rank Approximation.

Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Testing Matrix Rank, Optimally.

Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Sketching Algorithms for Genomic Data Analysis and Querying in a Secure Enclave.

Can Kockan, Kaiyuan Zhu, Natnatee Dokmai, Nikolai Karpov, M. Oguzhan Külekci, David P. Woodruff, Süleyman Cenk Sahinalp

Proceedings of the Research in Computational Molecular Biology, 2019

Weighted Reservoir Sampling from Distributed Streams.

Rajesh Jayaram, Gokarna Sharma, Srikanta Tirthapura, David P. Woodruff

Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

Average Case Column Subset Selection for Entrywise 퓁₁-Norm Loss.

Zhao Song, David P. Woodruff, Peilin Zhong

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Towards a Zero-One Law for Column Subset Selection.

Zhao Song, David P. Woodruff, Peilin Zhong

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Tight Dimensionality Reduction for Sketching Low Degree Polynomial Kernels.

Michela Meister, Tamás Sarlós, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Efficient and Thrifty Voting by Any Means Necessary.

Debmalya Mandal, Ariel D. Procaccia, Nisarg Shah, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Total Least Squares Regression in Input Sparsity Time.

Huaian Diao, Zhao Song, David P. Woodruff, Xin Yang

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Optimal Sketching for Kronecker Product Regression and Low Rank Approximation.

Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Regularized Weighted Low Rank Approximation.

Frank Ban, David P. Woodruff, Qiuyi (Richard) Zhang

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Dimensionality Reduction for Tukey Regression.

Kenneth L. Clarkson, Ruosong Wang, David P. Woodruff

Proceedings of the 36th International Conference on Machine Learning, 2019

Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-means Clustering.

Taisuke Yasuda, David P. Woodruff, Manuel Fernandez

Proceedings of the 36th International Conference on Machine Learning, 2019

Faster Algorithms for Binary Matrix Factorization.

Ravi Kumar, Rina Panigrahy, Ali Rahimi, David P. Woodruff

Proceedings of the 36th International Conference on Machine Learning, 2019

Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams.

David P. Woodruff, Guang Yang

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Robust Communication-Optimal Distributed Clustering Algorithms.

Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, David P. Woodruff

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

The One-Way Communication Complexity of Dynamic Time Warping Distance.

Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang

Proceedings of the 35th International Symposium on Computational Geometry, 2019

Sample-Optimal Low-Rank Approximation of Distance Matrices.

Piotr Indyk, Ali Vakilian, Tal Wagner, David P. Woodruff

Proceedings of the Conference on Learning Theory, 2019

Learning Two Layer Rectified Neural Networks in Polynomial Time.

Ainesh Bakshi, Rajesh Jayaram, David P. Woodruff

Proceedings of the Conference on Learning Theory, 2019

Faster Algorithms for High-Dimensional Robust Covariance Estimation.

Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff

Proceedings of the Conference on Learning Theory, 2019

The Query Complexity of Mastermind with l_p Distances.

Manuel Fernandez, David P. Woodruff, Taisuke Yasuda

Proceedings of the Approximation, 2019

Conditional Sparse $L_p$-norm Regression With Optimal Probability.

John Hainline, Brendan Juba, Hai S. Le, David P. Woodruff

Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

Sublinear Time Numerical Linear Algebra for Structured Matrices.

Xiaofei Shi, David P. Woodruff

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018

Frequency Moments.

David P. Woodruff

Proceedings of the Encyclopedia of Database Systems, Second Edition, 2018

Relative Error Tensor Low Rank Approximation.

Zhao Song, David P. Woodruff, Peilin Zhong

Electron. Colloquium Comput. Complex., 2018

Towards a Zero-One Law for Entrywise Low Rank Approximation.

Zhao Song, David P. Woodruff, Peilin Zhong

CoRR, 2018

A PTAS for 𝓁_p-Low Rank Approximation.

Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff

CoRR, 2018

Leveraging Well-Conditioned Bases: Streaming \& Distributed Summaries in Minkowski p-Norms.

Graham Cormode, Charlie Dickens, David P. Woodruff

CoRR, 2018

Conditional Sparse 𝓁_p-norm Regression With Optimal Probability.

John Hainline, Brendan Juba, Hai S. Le, David P. Woodruff

CoRR, 2018

Tight Bounds for 𝓁_p Oblivious Subspace Embeddings.

Ruosong Wang, David P. Woodruff

CoRR, 2018

Distributed Statistical Estimation of Matrix Products with Applications.

David P. Woodruff, Qin Zhang

Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

Data Streams with Bounded Deletions.

Rajesh Jayaram, David P. Woodruff

Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

On Coresets for Logistic Regression.

Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Robust Subspace Approximation in a Stream.

Roie Levin, Anish Prasad Sevekari, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Sublinear Time Low-Rank Approximation of Distance Matrices.

Ainesh Bakshi, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

An Empirical Evaluation of Sketching for Numerical Linear Algebra.

Yogesh Dahiya, Dimitris Konomis, David P. Woodruff

Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018

Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness.

Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Matrix Completion and Related Problems via Strong Duality.

Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, Hongyang Zhang

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski p-Norms.

Graham Cormode, Charlie Dickens, David P. Woodruff

Proceedings of the 35th International Conference on Machine Learning, 2018

Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order.

Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, Lin F. Yang

Proceedings of the 35th International Conference on Machine Learning, 2018

Improved Algorithms for Adaptive Compressed Sensing.

Vasileios Nakos, Xiaofei Shi, David P. Woodruff, Hongyang Zhang

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

High Probability Frequency Moment Sketches.

Sumit Ganguly, David P. Woodruff

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Revisiting Frequency Moment Estimation in Random Order Streams.

Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension.

Christian Sohler, David P. Woodruff

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Perfect Lp Sampling in a Data Stream.

Rajesh Jayaram, David P. Woodruff

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

On Sketching the q to p Norms.

Aditya Krishnan, Sidhanth Mohanty, David P. Woodruff

Proceedings of the Approximation, 2018

Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.

Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou

Proceedings of the Approximation, 2018

On Low-Risk Heavy Hitters and Sparse Recovery Schemes.

Yi Li, Vasileios Nakos, David P. Woodruff

Proceedings of the Approximation, 2018

Sketching for Kronecker Product Regression and P-splines.

Huaian Diao, Zhao Song, Wen Sun, David P. Woodruff

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018

2017

Faster Kernel Ridge Regression Using Sketching and Preconditioning.

Haim Avron, Kenneth L. Clarkson, David P. Woodruff

SIAM J. Matrix Anal. Appl., 2017

Optimal CUR Matrix Decompositions.

Christos Boutsidis, David P. Woodruff

SIAM J. Comput., 2017

Processing Big Data Streams (NII Shonan Meeting 2017-7).

Vladimir Braverman, David P. Woodruff, Ke Yi

NII Shonan Meet. Rep., 2017

When distributed computation is communication expensive.

David P. Woodruff, Qin Zhang

Distributed Comput., 2017

Theory and Applications of Hashing (Dagstuhl Seminar 17181).

Martin Dietzfelbinger, Michael Mitzenmacher, Rasmus Pagh, David P. Woodruff, Martin Aumüller

Dagstuhl Reports, 2017

Approximation Algorithms for ࡁ₀-Low Rank Approximation.

Karl Bringmann, Pavel Kolev, David P. Woodruff

CoRR, 2017

Fast Regression with an $\ell_\infty$ Guarantee.

Eric Price, Zhao Song, David P. Woodruff

CoRR, 2017

Optimal Sample Complexity for Matrix Completion and Related Problems via 𝓁s₂-Regularization.

Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, Hongyang Zhang

CoRR, 2017

Low rank approximation with entrywise l₁-norm error.

Zhao Song, David P. Woodruff, Peilin Zhong

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Adaptive Matrix Vector Product.

Santosh S. Vempala, David P. Woodruff

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Low-Rank PSD Approximation in Input-Sparsity Time.

Kenneth L. Clarkson, David P. Woodruff

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

BPTree: An ℓ₂ Heavy Hitters Algorithm Using Constant Memory.

Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff

Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017

Is Input Sparsity Time Possible for Kernel Low-Rank Approximation?

Cameron Musco, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Near Optimal Sketching of Low-Rank Tensor Regression.

Xingguo Li, Jarvis D. Haupt, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Approximation Algorithms for l₀-Low Rank Approximation.

Karl Bringmann, Pavel Kolev, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Algorithms for $\ell_p$ Low-Rank Approximation.

Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, David P. Woodruff

Proceedings of the 34th International Conference on Machine Learning, 2017

Fast Regression with an $ell_infty$ Guarantee.

Eric Price, Zhao Song, David P. Woodruff

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Embeddings of Schatten Norms with Applications to Data Streams.

Yi Li, David P. Woodruff

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices.

Cameron Musco, David P. Woodruff

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams.

Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Sketching for Geometric Problems (Invited Talk).

David P. Woodruff

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Sharper Bounds for Regularized Data Fitting.

Haim Avron, Kenneth L. Clarkson, David P. Woodruff

Proceedings of the Approximation, 2017

2016

A Simple Message-Optimal Algorithm for Random Sampling from a Distributed Stream.

Yung-Yu Chung, Srikanta Tirthapura, David P. Woodruff

IEEE Trans. Knowl. Data Eng., 2016

Editorial to the Special Issue on SODA'12.

Yuval Rabani, Andréa W. Richa, Jared Saia, David P. Woodruff

ACM Trans. Algorithms, 2016

Frequent Directions: Simple and Deterministic Matrix Sketching.

Mina Ghashami, Edo Liberty, Jeff M. Phillips, David P. Woodruff

SIAM J. Comput., 2016

The Fast Cauchy Transform and Faster Robust Linear Regression.

Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff

SIAM J. Comput., 2016

Recent Advances in Randomized Numerical Linear Algebra (NII Shonan Meeting 2016-10).

Ravindran Kannan, Michael W. Mahoney, David P. Woodruff

NII Shonan Meet. Rep., 2016

New Algorithms for Heavy Hitters in Data Streams.

David P. Woodruff

CoRR, 2016

Sharper Bounds for Regression and Low-Rank Approximation with Regularization.

Haim Avron, Kenneth L. Clarkson, David P. Woodruff

CoRR, 2016

Space-Efficient Estimation of Statistics Over Sub-Sampled Streams.

Andrew McGregor, A. Pavan, Srikanta Tirthapura, David P. Woodruff

Algorithmica, 2016

Certifying Equality With Limited Interaction.

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev

Algorithmica, 2016

Guest Editorial for Information Complexity and Applications.

Mark Braverman, David P. Woodruff

Algorithmica, 2016

Weighted low rank approximations with provable guarantees.

Ilya P. Razenshteyn, Zhao Song, David P. Woodruff

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

On approximating functions of the singular values in a stream.

Yi Li, David P. Woodruff

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Communication lower bounds for statistical estimation problems via a distributed data processing inequality.

Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Beating CountSketch for heavy hitters in insertion streams.

Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Optimal principal component analysis in distributed and streaming models.

Christos Boutsidis, David P. Woodruff, Peilin Zhong

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond.

Hossein Esfandiari, MohammadTaghi Hajiaghayi, David P. Woodruff

Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016

Nearly-optimal bounds for sparse recovery in generic norms, with applications to <i>k</i>-median sketching.

Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, David P. Woodruff

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors.

Vladimir Braverman, Stephen R. Chestnut, David P. Woodruff, Lin F. Yang

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems.

Arnab Bhattacharyya, Palash Dey, David P. Woodruff

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Sublinear Time Orthogonal Tensor Decomposition.

Zhao Song, David P. Woodruff, Huan Zhang

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Communication-Optimal Distributed Clustering.

Jiecao Chen, He Sun, David P. Woodruff, Qin Zhang

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Communication Efficient Distributed Kernel Principal Component Analysis.

Maria-Florina Balcan, Yingyu Liang, Le Song, David P. Woodruff, Bo Xie

Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016

On Sketching Quadratic Forms.

Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

How to Fake Multiply by a Gaussian Matrix.

Michael Kapralov, Vamsi K. Potluru, David P. Woodruff

Proceedings of the 33nd International Conference on Machine Learning, 2016

New Algorithms for Heavy Hitters in Data Streams (Invited Talk).

David P. Woodruff

Proceedings of the 19th International Conference on Database Theory, 2016

Distributed low rank approximation of implicit functions of a matrix.

David P. Woodruff, Peilin Zhong

Proceedings of the 32nd IEEE International Conference on Data Engineering, 2016

Optimal Approximate Matrix Product in Terms of Stable Rank.

Michael B. Cohen, Jelani Nelson, David P. Woodruff

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Stochastic Streams: Sample Complexity vs. Space Complexity.

Michael S. Crouch, Andrew McGregor, Gregory Valiant, David P. Woodruff

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

New Characterizations in Turnstile Streams with Applications.

Yuqing Ai, Wei Hu, Yi Li, David P. Woodruff

Proceedings of the 31st Conference on Computational Complexity, 2016

Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings.

Yi Li, David P. Woodruff

Proceedings of the Approximation, 2016

2015

The Simultaneous Communication of Disjointness with Applications to Data Streams.

Omri Weinstein, David P. Woodruff

Electron. Colloquium Comput. Complex., 2015

Amplification of One-Way Information Complexity via Codes and Noise Sensitivity.

Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev

Electron. Colloquium Comput. Complex., 2015

Applications of Uniform Sampling: Densest Subgraph and Beyond.

Hossein Esfandiari, MohammadTaghi Hajiaghayi, David P. Woodruff

CoRR, 2015

Communication-optimal Distributed Principal Component Analysis in the Column-partition Model.

Christos Boutsidis, David P. Woodruff

CoRR, 2015

Distributed Kernel Principal Component Analysis.

Maria-Florina Balcan, Yingyu Liang, Le Song, David P. Woodruff, Bo Xie

CoRR, 2015

Nearly-optimal bounds for sparse recovery in generic norms, with applications to $k$-median sketching.

Arturs Backurs, Piotr Indyk, Eric Price, Ilya P. Razenshteyn, David P. Woodruff

CoRR, 2015

A General Method for Estimating Correlated Aggregates Over a Data Stream.

Srikanta Tirthapura, David P. Woodruff

Algorithmica, 2015

Sketching for <i>M</i>-Estimators: A Unified Approach to Robust Regression.

Kenneth L. Clarkson, David P. Woodruff

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication.

Dirk Van Gucht, Ryan Williams, David P. Woodruff, Qin Zhang

Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

Input Sparsity and Hardness for Robust Subspace Approximation.

Kenneth L. Clarkson, David P. Woodruff

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Tight Bounds for Graph Problems in Insertion Streams.

Xiaoming Sun, David P. Woodruff

Proceedings of the Approximation, 2015

2014

Sketching as a Tool for Numerical Linear Algebra.

David P. Woodruff

Found. Trends Theor. Comput. Sci., 2014

Data Streams and Applications in Computer Science.

David P. Woodruff

Bull. EATCS, 2014

A Sketching Algorithm for Spectral Graph Sparsification.

Jiecao Chen, Bo Qin, David P. Woodruff, Qin Zhang

CoRR, 2014

The Sketching Complexity of Graph Cuts.

Alexandr Andoni, Robert Krauthgamer, David P. Woodruff

CoRR, 2014

Steiner transitive-closure spanners of low-dimensional posets.

Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev

Comb., 2014

On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model.

Yi Li, Xiaoming Sun, Chengu Wang, David P. Woodruff

Proceedings of the Distributed Computing - 28th International Symposium, 2014

Turnstile streaming algorithms might as well be linear sketches.

Yi Li, Huy L. Nguyen, David P. Woodruff

Proceedings of the Symposium on Theory of Computing, 2014

An Optimal Lower Bound for Distinct Elements in the Message Passing Model.

David P. Woodruff, Qin Zhang

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

On Sketching Matrix Norms and the Top Singular Vector.

Yi Li, Huy L. Nguyen, David P. Woodruff

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Is min-wise hashing optimal for summarizing set intersection?

Rasmus Pagh, Morten Stöckel, David P. Woodruff

Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

Spanners and sparsifiers in dynamic streams.

Michael Kapralov, David P. Woodruff

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Beyond set disjointness: the communication complexity of finding the intersection.

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Low Rank Approximation Lower Bounds in Row-Update Streams.

David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Improved Distributed Principal Component Analysis.

Yingyu Liang, Maria-Florina Balcan, Vandana Kanchanapally, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Subspace Embeddings for the Polynomial Kernel.

Haim Avron, Huy L. Nguyen, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Improved testing of low rank matrices.

Yi Li, Zhengyu Wang, David P. Woodruff

Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014

Principal Component Analysis and Higher Correlations for Distributed Data.

Ravi Kannan, Santosh S. Vempala, David P. Woodruff

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error.

T. S. Jayram, David P. Woodruff

ACM Trans. Algorithms, 2013

Multi-Tuple Deletion Propagation: Approximations and Complexity.

Benny Kimelfeld, Jan Vondrák, David P. Woodruff

Proc. VLDB Endow., 2013

Subspace Embeddings and ℓ_p-Regression Using Exponential Random Variables

David P. Woodruff, Qin Zhang

CoRR, 2013

When Distributed Computation does not Help

David P. Woodruff, Qin Zhang

CoRR, 2013

How robust are linear sketches to adaptive inputs?

Moritz Hardt, David P. Woodruff

Proceedings of the Symposium on Theory of Computing Conference, 2013

Low rank approximation and regression in input sparsity time.

Kenneth L. Clarkson, David P. Woodruff

Proceedings of the Symposium on Theory of Computing Conference, 2013

Lower Bounds for Adaptive Sparse Recovery.

Eric Price, David P. Woodruff

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching.

Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Sketching Structured Matrices for Faster Nonlinear Regression.

Haim Avron, Vikas Sindhwani, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

Subspace Embeddings and \(\ell_p\)-Regression Using Exponential Random Variables.

David P. Woodruff, Qin Zhang

Proceedings of the COLT 2013, 2013

A Tight Lower Bound for High Frequency Moment Estimation with Small Error.

Yi Li, David P. Woodruff

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners.

Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

SIAM J. Discret. Math., 2012

Transitive-Closure Spanners.

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

SIAM J. Comput., 2012

Fast approximation of matrix coherence and statistical leverage.

Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff

J. Mach. Learn. Res., 2012

A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field.

David P. Woodruff

J. Comput. Sci. Technol., 2012

Sublinear optimization for machine learning.

Kenneth L. Clarkson, Elad Hazan, David P. Woodruff

J. ACM, 2012

The Fast Cauchy Transform: with Applications to Basis Construction, Regression, and Subspace Approximation in L1

Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff

CoRR, 2012

Tight bounds for distributed functional monitoring.

David P. Woodruff, Qin Zhang

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Reusable low-error compressive sampling schemes through privacy.

Anna C. Gilbert, Brett Hemenway, Martin J. Strauss, David P. Woodruff, Mary Wootters

Proceedings of the IEEE Statistical Signal Processing Workshop, 2012

Rectangle-efficient aggregation in spatial data streams.

Srikanta Tirthapura, David P. Woodruff

Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

Applications of the Shannon-Hartley theorem to data streams and sparse recovery.

Eric Price, David P. Woodruff

Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012

On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation.

Jelani Nelson, Huy L. Nguyên, David P. Woodruff

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Optimal Random Sampling from Distributed Streams Revisited.

Srikanta Tirthapura, David P. Woodruff

Proceedings of the Distributed Computing - 25th International Symposium, 2011

Near-optimal private approximation protocols via a black box transformation.

David P. Woodruff

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Subspace embeddings for the L₁-norm with applications.

Christian Sohler, David P. Woodruff

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Fast moment estimation in data streams in optimal space.

Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error.

T. S. Jayram, David P. Woodruff

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

The Complexity of Linear Dependence Problems in Vector Spaces.

Arnab Bhattacharyya, Piotr Indyk, David P. Woodruff, Ning Xie

Proceedings of the Innovations in Computer Science, 2011

(1 + eps)-Approximate Sparse Recovery.

Eric Price, David P. Woodruff

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

On the Power of Adaptivity in Sparse Recovery.

Piotr Indyk, Eric Price, David P. Woodruff

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Tolerant Algorithms.

Rolf Klein, Rainer Penninger, Christian Sohler, David P. Woodruff

Proceedings of the Algorithms - ESA 2011, 2011

Streaming Algorithms with One-Sided Estimation.

Joshua Brody, David P. Woodruff

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Epistemic privacy.

Alexandre V. Evfimievski, Ronald Fagin, David P. Woodruff

J. ACM, 2010

Steiner Transitive-Closure Spanners of d-Dimensional Posets

Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev

CoRR, 2010

1-Pass Relative-Error L_p-Sampling with Applications.

Morteza Monemizadeh, David P. Woodruff

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

On the Exact Space Complexity of Sketching and Streaming Small Norms.

Daniel M. Kane, Jelani Nelson, David P. Woodruff

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Coresets and Sketches for High Dimensional Subspace Approximation Problems.

Dan Feldman, Morteza Monemizadeh, Christian Sohler, David P. Woodruff

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Lower Bounds for Sparse Recovery.

Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Fast Manhattan sketches in data streams.

Jelani Nelson, David P. Woodruff

Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

An optimal algorithm for the distinct elements problem.

Daniel M. Kane, Jelani Nelson, David P. Woodruff

Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

Additive Spanners in Nearly Quadratic Time.

David P. Woodruff

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Frequency Moments.

David P. Woodruff

Proceedings of the Encyclopedia of Database Systems, 2009

Transitive-Closure Spanners of the Hypercube and the Hypergrid.

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

Electron. Colloquium Comput. Complex., 2009

A Near-Optimal Algorithm for L1-Difference

Jelani Nelson, David P. Woodruff

CoRR, 2009

Numerical linear algebra in the streaming model.

Kenneth L. Clarkson, David P. Woodruff

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

The average-case complexity of counting distinct elements.

David P. Woodruff

Proceedings of the Database Theory, 2009

The Data Stream Space Complexity of Cascaded Norms.

T. S. Jayram, David P. Woodruff

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Efficient Sketches for Earth-Mover Distance, with Applications.

Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

Revisiting Norm Estimation in Data Streams

Daniel M. Kane, Jelani Nelson, David P. Woodruff

CoRR, 2008

Corruption and Recovery-Efficient Locally Decodable Codes.

David P. Woodruff

Proceedings of the Approximation, 2008

2007

Efficient and private distance approximation in the communication and streaming models.

David P. Woodruff

PhD thesis, 2007

A Geometric Approach to Information-Theoretic Private Information Retrieval.

David P. Woodruff, Sergey Yekhanin

SIAM J. Comput., 2007

New Lower Bounds for General Locally Decodable Codes.

David P. Woodruff

Electron. Colloquium Comput. Complex., 2007

The communication and streaming complexity of computing the longest common and increasing subsequences.

Xiaoming Sun, David P. Woodruff

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Revisiting the Efficiency of Malicious Two-Party Computation.

David P. Woodruff

IACR Cryptol. ePrint Arch., 2006

Fast Algorithms for the Free Riders Problem in Broadcast Encryption.

Zulfikar Ramzan, David P. Woodruff

IACR Cryptol. ePrint Arch., 2006

Lower Bounds for Additive Spanners, Emulators, and More.

David P. Woodruff

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Explicit Exclusive Set Systems with Applications to Broadcast Encryption.

Craig Gentry, Zulfikar Ramzan, David P. Woodruff

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Better Approximations for the Minimum Common Integer Partition Problem.

David P. Woodruff

Proceedings of the Approximation, 2006

2005

Polylogarithmic Private Approximations and Efficient Matching

Piotr Indyk, David P. Woodruff

Electron. Colloquium Comput. Complex., 2005

Optimal approximations of the frequency moments of data streams.

Piotr Indyk, David P. Woodruff

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004

Private Inference Control.

David P. Woodruff, Jessica Staddon

IACR Cryptol. ePrint Arch., 2004

Practical Cryptography in High Dimensional Tori.

Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, David P. Woodruff

IACR Cryptol. ePrint Arch., 2004

Optimal space lower bounds for all frequency moments.

David P. Woodruff

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Clustering via Matrix Powering.

Hanson Zhou, David P. Woodruff

Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

Asymptotically Optimal Communication for Torus-Based Cryptography.

Marten van Dijk, David P. Woodruff

Proceedings of the Advances in Cryptology, 2004

2003

Tight Lower Bounds for the Distinct Elements Problem.

Piotr Indyk, David P. Woodruff

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

Cryptography in an Unbounded Computational Model.

David P. Woodruff, Marten van Dijk

Proceedings of the Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28, 2002