# David P. Woodruff

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

Collaborative distances:

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

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

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

Tight Bounds for the Subspace Sketch Problem with Applications.
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

Graph Spanners in the Message-Passing Model.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

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

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

Pseudo-deterministic Streaming.
Electronic Colloquium on Computational Complexity (ECCC), 2019

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

Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation.
CoRR, 2019

Regularized Weighted Low Rank Approximation.
CoRR, 2019

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

Low-Rank Approximation from Communication Complexity.
CoRR, 2019

Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
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 𝓁1-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

Querying a Matrix Through Matrix-Vector Products.
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 INFORMATIK 2019: 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 lp 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.
Electronic Colloquium on Computational Complexity (ECCC), 2018

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

Perfect Lp Sampling in a Data Stream.
CoRR, 2018

A PTAS for 𝓁p-Low Rank Approximation.
CoRR, 2018

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

Conditional Sparse 𝓁p-norm Regression With Optimal Probability.
CoRR, 2018

Tight Bounds for 𝓁p 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 Analysis Applications, 2017

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

When distributed computation is communication expensive.
Distributed Computing, 2017

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

Approximation Algorithms for ࡁ0-Low Rank Approximation.
CoRR, 2017

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

Optimal Sample Complexity for Matrix Completion and Related Problems via 𝓁s2-Regularization.
CoRR, 2017

Low rank approximation with entrywise l1-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 ℓ2 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 l0-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 k-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.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Amplification of One-Way Information Complexity via Codes and Noise Sensitivity.
Electronic Colloquium on Computational Complexity (ECCC), 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 M-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.
Foundations and Trends in Theoretical Computer Science, 2014

Data Streams and Applications in Computer Science.
Bulletin of the 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.
Combinatorica, 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.
PVLDB, 2013

Subspace Embeddings and ℓp-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. Discrete 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 L1-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 Lp-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.
Electronic Colloquium on Computational Complexity (ECCC), 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.
Electronic Colloquium on Computational Complexity (ECCC), 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 Cryptology ePrint Archive, 2006

Fast Algorithms for the Free Riders Problem in Broadcast Encryption.
IACR Cryptology ePrint Archive, 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
Electronic Colloquium on Computational Complexity (ECCC), 2005

A Geometric Approach to Information-Theoretic Private Information Retrieval
Electronic Colloquium on Computational Complexity (ECCC), 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 Cryptology ePrint Archive, 2004

Practical Cryptography in High Dimensional Tori.
IACR Cryptology ePrint Archive, 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