# David P. Woodruff

Affiliations:
• Carnegie Mellon University, PA, USA
• IBM Almaden Research Center (former)

According to our database1, David P. Woodruff authored at least 286 papers between 2002 and 2022.

Collaborative distances:
• Dijkstra number2 of three.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2022
Tight Bounds for ℓ<sub>1</sub> Oblivious Subspace Embeddings.
ACM Trans. Algorithms, 2022

Memory Bounds for the Experts Problem.
CoRR, 2022

The White-Box Adversarial Data Stream Model.
CoRR, 2022

Sketching Algorithms and Lower Bounds for Ridge Regression.
CoRR, 2022

High-Dimensional Geometric Streaming in Polynomial Space.
CoRR, 2022

Testing Positive Semidefiniteness Using Linear Measurements.
CoRR, 2022

Triangle and Four Cycle Counting with Predictions in Graph Streams.
CoRR, 2022

Fast Regression for Structured Inputs.
CoRR, 2022

Low-Rank Approximation with 1/ε<sup>1/3</sup> Matrix-Vector Products.
CoRR, 2022

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

Improved Algorithms for Low Rank Approximation from Sparsity.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Frequency Estimation with One-Sided Error.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time.
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.
Proceedings of the Research in Computational Molecular Biology, 2022

Noisy Boolean Hidden Matching with Applications.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021
How to Reduce Dimension With PCA and Random Projections?
IEEE Trans. Inf. Theory, 2021

Querying a Matrix through Matrix-Vector Products.
ACM Trans. Algorithms, 2021

A Framework for Adversarially Robust Streaming Algorithms.
SIGMOD Rec., 2021

Tight Bounds for the Subspace Sketch Problem with Applications.
SIAM J. Comput., 2021

Perfect L<sub>p</sub> Sampling in a Data Stream.
SIAM J. Comput., 2021

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

Learning-Augmented k-means Clustering.
CoRR, 2021

Truly Perfect Samplers for Data Streams and Sliding Windows.
CoRR, 2021

Streaming and Distributed Algorithms for Robust Column Subset Selection.
CoRR, 2021

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

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

Exponentially Improved Dimensionality Reduction for 𝓁<sub>1</sub>: Subspace Embeddings and Independence Testing.
CoRR, 2021

Learning-Augmented Sketches for Hessians.
CoRR, 2021

Non-PSD matrix sketching with applications to regression and optimization.
Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, 2021

Hutch++: Optimal Stochastic Trace Estimation.
Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Optimal <i>ℓ</i><sub>1</sub> Column Subset Selection and a Fast PTAS for Low Rank Approximation.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Subspace Exploration: Bounds on Projected Frequency Estimation.
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.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Optimal Sketching for Trace Estimation.
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.
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.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Oblivious Sketching for Logistic Regression.
Proceedings of the 38th International Conference on Machine Learning, 2021

Single Pass Entrywise-Transformed Low Rank Approximation.
Proceedings of the 38th International Conference on Machine Learning, 2021

Streaming and Distributed Algorithms for Robust Column Subset Selection.
Proceedings of the 38th International Conference on Machine Learning, 2021

In-Database Regression in Input Sparsity Time.
Proceedings of the 38th International Conference on Machine Learning, 2021

Dimensionality Reduction for the Sum-of-Distances Metric.
Proceedings of the 38th International Conference on Machine Learning, 2021

Fast Sketching of Polynomial Kernels of Polynomial Degree.
Proceedings of the 38th International Conference on Machine Learning, 2021

Learning a Latent Simplex in Input Sparsity Time.
Proceedings of the 9th International Conference on Learning Representations, 2021

Separations for Estimating Large Frequency Moments on Data Streams.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

A Very Sketchy Talk (Invited Talk).
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Average-Case Communication Complexity of Statistical Problems.
Proceedings of the Conference on Learning Theory, 2021

Exponentially Improved Dimensionality Reduction for l1: Subspace Embeddings and Independence Testing.
Proceedings of the Conference on Learning Theory, 2021

Reduced-Rank Regression with Operator Norm Error.
Proceedings of the Conference on Learning Theory, 2021

A Simple Proof of a New Set Disjointness with Applications to Data Streams.
Proceedings of the 36th Computational Complexity Conference, 2021

The Product of Gaussian Matrices Is Close to Gaussian.
Proceedings of the Approximation, 2021

2020
Introduction to the Special Issue on SODA'18.
ACM Trans. Algorithms, 2020

The Coin Problem with Applications to Data Streams.
Electron. Colloquium Comput. Complex., 2020

Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes.
CoRR, 2020

Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra.
CoRR, 2020

Optimal 𝓁<sub>1</sub> Column Subset Selection and a Fast PTAS for Low Rank Approximation.
CoRR, 2020

On Learned Sketches for Randomized Numerical Linear Algebra.
CoRR, 2020

WOR and p's: Sketches for 𝓁<sub>p</sub>-Sampling Without Replacement.
CoRR, 2020

Approximation Algorithms for Sparse Principal Component Analysis.
CoRR, 2020

Average Case Column Subset Selection for Entrywise 𝓁<sub>1</sub>-Norm Loss.
CoRR, 2020

LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew.
Proceedings of the WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, 2020

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

The Communication Complexity of Optimization.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Oblivious Sketching of High-Degree Polynomial Kernels.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

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.
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 ℓ<sub>p</sub>-Sampling Without Replacement.
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.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling.
Proceedings of the 37th International Conference on Machine Learning, 2020

Input-Sparsity Low Rank Approximation in Schatten Norm.
Proceedings of the 37th International Conference on Machine Learning, 2020

Learning-Augmented Data Stream Algorithms.
Proceedings of the 8th International Conference on Learning Representations, 2020

Span Recovery for Deep Neural Networks with Applications to Input Obfuscation.
Proceedings of the 8th International Conference on Learning Representations, 2020

Near Optimal Linear Algebra in the Online and Sliding Window Models.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Robust and Sample Optimal Algorithms for PSD Low Rank Approximation.
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.
Proceedings of the Approximation, 2020

Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
Proceedings of the Approximation, 2020

Streaming Complexity of SVMs.
Proceedings of the Approximation, 2020

Automatic Differentiation of Sketched Regression.
Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

Optimal Deterministic Coresets for Ridge Regression.
Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019
An Optimal Algorithm for ℓ<sub>1</sub>-Heavy Hitters in Insertion Streams and Related Problems.
ACM Trans. Algorithms, 2019

On Approximating Matrix Norms in Data Streams.
SIAM J. Comput., 2019

Non-Convex Matrix Completion and Related Problems via Strong Duality.
J. Mach. Learn. Res., 2019

Pseudo-deterministic Streaming.
Electron. Colloquium Comput. Complex., 2019

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

Oblivious Sketching of High-Degree Polynomial Kernels.
CoRR, 2019

Low-Rank Approximation from Communication Complexity.
CoRR, 2019

Tight Bounds for ℓp Oblivious Subspace Embeddings.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A PTAS for ℓp-Low Rank Approximation.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Testing Matrix Rank, Optimally.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Sketching Algorithms for Genomic Data Analysis and Querying in a Secure Enclave.
Proceedings of the Research in Computational Molecular Biology, 2019

Weighted Reservoir Sampling from Distributed Streams.
Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

Average Case Column Subset Selection for Entrywise 퓁<sub>1</sub>-Norm Loss.
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.
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.
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.
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.
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.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Regularized Weighted Low Rank Approximation.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Dimensionality Reduction for Tukey Regression.
Proceedings of the 36th International Conference on Machine Learning, 2019

Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-means Clustering.
Proceedings of the 36th International Conference on Machine Learning, 2019

Faster Algorithms for Binary Matrix Factorization.
Proceedings of the 36th International Conference on Machine Learning, 2019

Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Robust Communication-Optimal Distributed Clustering Algorithms.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

On Coresets for Logistic Regression.
Proceedings of the 49. Jahrestagung der Gesellschaft für Informatik, 50 Jahre Gesellschaft für Informatik, 2019

The One-Way Communication Complexity of Dynamic Time Warping Distance.
Proceedings of the 35th International Symposium on Computational Geometry, 2019

Sample-Optimal Low-Rank Approximation of Distance Matrices.
Proceedings of the Conference on Learning Theory, 2019

Learning Two Layer Rectified Neural Networks in Polynomial Time.
Proceedings of the Conference on Learning Theory, 2019

Faster Algorithms for High-Dimensional Robust Covariance Estimation.
Proceedings of the Conference on Learning Theory, 2019

Towards Optimal Moment Estimation in Streaming and Distributed Models.
Proceedings of the Approximation, 2019

The Query Complexity of Mastermind with l<sub>p</sub> Distances.
Proceedings of the Approximation, 2019

Conditional Sparse $L_p$-norm Regression With Optimal Probability.
Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

Sublinear Time Numerical Linear Algebra for Structured Matrices.
Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018
Frequency Moments.
Proceedings of the Encyclopedia of Database Systems, Second Edition, 2018

Relative Error Tensor Low Rank Approximation.
Electron. Colloquium Comput. Complex., 2018

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

A PTAS for 𝓁<sub>p</sub>-Low Rank Approximation.
CoRR, 2018

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

Conditional Sparse 𝓁<sub>p</sub>-norm Regression With Optimal Probability.
CoRR, 2018

Tight Bounds for 𝓁<sub>p</sub> Oblivious Subspace Embeddings.
CoRR, 2018

Distributed Statistical Estimation of Matrix Products with Applications.
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

Data Streams with Bounded Deletions.
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

Robust Subspace Approximation in a Stream.
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.
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.
Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018

Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Matrix Completion and Related Problems via Strong Duality.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski p-Norms.
Proceedings of the 35th International Conference on Machine Learning, 2018

Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order.
Proceedings of the 35th International Conference on Machine Learning, 2018

Improved Algorithms for Adaptive Compressed Sensing.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

High Probability Frequency Moment Sketches.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Revisiting Frequency Moment Estimation in Random Order Streams.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Perfect Lp Sampling in a Data Stream.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

On Sketching the q to p Norms.
Proceedings of the Approximation, 2018

Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.
Proceedings of the Approximation, 2018

On Low-Risk Heavy Hitters and Sparse Recovery Schemes.
Proceedings of the Approximation, 2018

Sketching for Kronecker Product Regression and P-splines.
Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018

2017
Faster Kernel Ridge Regression Using Sketching and Preconditioning.
SIAM J. Matrix Anal. Appl., 2017

Optimal CUR Matrix Decompositions.
SIAM J. Comput., 2017

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

When distributed computation is communication expensive.
Distributed Comput., 2017

Theory and Applications of Hashing (Dagstuhl Seminar 17181).
Dagstuhl Reports, 2017

Approximation Algorithms for ࡁ<sub>0</sub>-Low Rank Approximation.
CoRR, 2017

Fast Regression with an $\ell_\infty$ Guarantee.
CoRR, 2017

Optimal Sample Complexity for Matrix Completion and Related Problems via 𝓁s<sub>2</sub>-Regularization.
CoRR, 2017

Low rank approximation with entrywise l<sub>1</sub>-norm error.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

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

Low-Rank PSD Approximation in Input-Sparsity Time.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

BPTree: An ℓ<sub>2</sub> Heavy Hitters Algorithm Using Constant Memory.
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?
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.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Approximation Algorithms for l<sub>0</sub>-Low Rank Approximation.
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.
Proceedings of the 34th International Conference on Machine Learning, 2017

Fast Regression with an $ell_infty$ Guarantee.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Embeddings of Schatten Norms with Applications to Data Streams.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices.
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.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Sketching for Geometric Problems (Invited Talk).
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Sharper Bounds for Regularized Data Fitting.
Proceedings of the Approximation, 2017

2016
A Simple Message-Optimal Algorithm for Random Sampling from a Distributed Stream.
IEEE Trans. Knowl. Data Eng., 2016

Editorial to the Special Issue on SODA'12.
ACM Trans. Algorithms, 2016

Frequent Directions: Simple and Deterministic Matrix Sketching.
SIAM J. Comput., 2016

The Fast Cauchy Transform and Faster Robust Linear Regression.
SIAM J. Comput., 2016

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

New Algorithms for Heavy Hitters in Data Streams.
CoRR, 2016

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

Space-Efficient Estimation of Statistics Over Sub-Sampled Streams.
Algorithmica, 2016

Certifying Equality With Limited Interaction.
Algorithmica, 2016

Guest Editorial for Information Complexity and Applications.
Algorithmica, 2016

Weighted low rank approximations with provable guarantees.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

On approximating functions of the singular values in a stream.
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.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Beating CountSketch for heavy hitters in insertion streams.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Optimal principal component analysis in distributed and streaming models.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond.
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.
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.
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.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Sublinear Time Orthogonal Tensor Decomposition.
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Communication-Optimal Distributed Clustering.
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.
Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016

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

How to Fake Multiply by a Gaussian Matrix.
Proceedings of the 33nd International Conference on Machine Learning, 2016

New Algorithms for Heavy Hitters in Data Streams (Invited Talk).
Proceedings of the 19th International Conference on Database Theory, 2016

Distributed low rank approximation of implicit functions of a matrix.
Proceedings of the 32nd IEEE International Conference on Data Engineering, 2016

Optimal Approximate Matrix Product in Terms of Stable Rank.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Stochastic Streams: Sample Complexity vs. Space Complexity.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

New Characterizations in Turnstile Streams with Applications.
Proceedings of the 31st Conference on Computational Complexity, 2016

Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings.
Proceedings of the Approximation, 2016

2015
The Simultaneous Communication of Disjointness with Applications to Data Streams.
Electron. Colloquium Comput. Complex., 2015

Amplification of One-Way Information Complexity via Codes and Noise Sensitivity.
Electron. Colloquium Comput. Complex., 2015

Applications of Uniform Sampling: Densest Subgraph and Beyond.
CoRR, 2015

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

Distributed Kernel Principal Component Analysis.
CoRR, 2015

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

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

Sketching for <i>M</i>-Estimators: A Unified Approach to Robust Regression.
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.
Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

Input Sparsity and Hardness for Robust Subspace Approximation.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Tight Bounds for Graph Problems in Insertion Streams.
Proceedings of the Approximation, 2015

2014
Sketching as a Tool for Numerical Linear Algebra.
Found. Trends Theor. Comput. Sci., 2014

Data Streams and Applications in Computer Science.
Bull. EATCS, 2014

A Sketching Algorithm for Spectral Graph Sparsification.
CoRR, 2014

The Sketching Complexity of Graph Cuts.
CoRR, 2014

Steiner transitive-closure spanners of low-dimensional posets.
Comb., 2014

On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model.
Proceedings of the Distributed Computing - 28th International Symposium, 2014

Turnstile streaming algorithms might as well be linear sketches.
Proceedings of the Symposium on Theory of Computing, 2014

An Optimal Lower Bound for Distinct Elements in the Message Passing Model.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

On Sketching Matrix Norms and the Top Singular Vector.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Is min-wise hashing optimal for summarizing set intersection?
Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

Spanners and sparsifiers in dynamic streams.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Beyond set disjointness: the communication complexity of finding the intersection.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Low Rank Approximation Lower Bounds in Row-Update Streams.
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Improved Distributed Principal Component Analysis.
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.
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.
Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014

Principal Component Analysis and Higher Correlations for Distributed Data.
Proceedings of The 27th Conference on Learning Theory, 2014

2013
Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error.
ACM Trans. Algorithms, 2013

Multi-Tuple Deletion Propagation: Approximations and Complexity.
Proc. VLDB Endow., 2013

Subspace Embeddings and ℓ<sub>p</sub>-Regression Using Exponential Random Variables
CoRR, 2013

When Distributed Computation does not Help
CoRR, 2013

How robust are linear sketches to adaptive inputs?
Proceedings of the Symposium on Theory of Computing Conference, 2013

Low rank approximation and regression in input sparsity time.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Lower Bounds for Adaptive Sparse Recovery.
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.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Sketching Structured Matrices for Faster Nonlinear Regression.
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.
Proceedings of the COLT 2013, 2013

A Tight Lower Bound for High Frequency Moment Estimation with Small Error.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners.
SIAM J. Discret. Math., 2012

Transitive-Closure Spanners.
SIAM J. Comput., 2012

Fast approximation of matrix coherence and statistical leverage.
J. Mach. Learn. Res., 2012

A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field.
J. Comput. Sci. Technol., 2012

Sublinear optimization for machine learning.
J. ACM, 2012

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

Tight bounds for distributed functional monitoring.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Reusable low-error compressive sampling schemes through privacy.
Proceedings of the IEEE Statistical Signal Processing Workshop, 2012

Rectangle-efficient aggregation in spatial data streams.
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.
Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012

On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
Optimal Random Sampling from Distributed Streams Revisited.
Proceedings of the Distributed Computing - 25th International Symposium, 2011

Near-optimal private approximation protocols via a black box transformation.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Subspace embeddings for the L<sub>1</sub>-norm with applications.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Fast moment estimation in data streams in optimal space.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

The Complexity of Linear Dependence Problems in Vector Spaces.
Proceedings of the Innovations in Computer Science, 2011

(1 + eps)-Approximate Sparse Recovery.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

On the Power of Adaptivity in Sparse Recovery.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Tolerant Algorithms.
Proceedings of the Algorithms - ESA 2011, 2011

Streaming Algorithms with One-Sided Estimation.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Epistemic privacy.
J. ACM, 2010

Steiner Transitive-Closure Spanners of d-Dimensional Posets
CoRR, 2010

1-Pass Relative-Error L<sub>p</sub>-Sampling with Applications.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

On the Exact Space Complexity of Sketching and Streaming Small Norms.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Coresets and Sketches for High Dimensional Subspace Approximation Problems.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Lower Bounds for Sparse Recovery.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Fast Manhattan sketches in data streams.
Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

An optimal algorithm for the distinct elements problem.
Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

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

2009
Frequency Moments.
Proceedings of the Encyclopedia of Database Systems, 2009

Transitive-Closure Spanners of the Hypercube and the Hypergrid.
Electron. Colloquium Comput. Complex., 2009

A Near-Optimal Algorithm for L1-Difference
CoRR, 2009

Numerical linear algebra in the streaming model.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

The average-case complexity of counting distinct elements.
Proceedings of the Database Theory, 2009

The Data Stream Space Complexity of Cascaded Norms.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Efficient Sketches for Earth-Mover Distance, with Applications.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008
Revisiting Norm Estimation in Data Streams
CoRR, 2008

Corruption and Recovery-Efficient Locally Decodable Codes.
Proceedings of the Approximation, 2008

2007
Efficient and private distance approximation in the communication and streaming models.
PhD thesis, 2007

New Lower Bounds for General Locally Decodable Codes.
Electron. Colloquium Comput. Complex., 2007

The communication and streaming complexity of computing the longest common and increasing subsequences.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006
Revisiting the Efficiency of Malicious Two-Party Computation.
IACR Cryptol. ePrint Arch., 2006

Fast Algorithms for the Free Riders Problem in Broadcast Encryption.
IACR Cryptol. ePrint Arch., 2006

Lower Bounds for Additive Spanners, Emulators, and More.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Explicit Exclusive Set Systems with Applications to Broadcast Encryption.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Better Approximations for the Minimum Common Integer Partition Problem.
Proceedings of the Approximation, 2006

2005
Polylogarithmic Private Approximations and Efficient Matching
Electron. Colloquium Comput. Complex., 2005

A Geometric Approach to Information-Theoretic Private Information Retrieval
Electron. Colloquium Comput. Complex., 2005

Optimal approximations of the frequency moments of data streams.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004
Private Inference Control.
IACR Cryptol. ePrint Arch., 2004

Practical Cryptography in High Dimensional Tori.
IACR Cryptol. ePrint Arch., 2004

Optimal space lower bounds for all frequency moments.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Clustering via Matrix Powering.
Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

Asymptotically Optimal Communication for Torus-Based Cryptography.
Proceedings of the Advances in Cryptology, 2004

2003
Tight Lower Bounds for the Distinct Elements Problem.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002
Cryptography in an Unbounded Computational Model.
Proceedings of the Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28, 2002