David P. Woodruff

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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2018
Relative Error Tensor Low Rank Approximation.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Learning Two Layer Rectified Neural Networks in Polynomial Time.
CoRR, 2018

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

Testing Matrix Rank, Optimally.
CoRR, 2018

Sublinear Time Low-Rank Approximation of Distance Matrices.
CoRR, 2018

Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension.
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

Distributed Statistical Estimation of Matrix Products with Applications.
CoRR, 2018

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

On Sketching the q to p norms.
CoRR, 2018

High Probability Frequency Moment Sketches.
CoRR, 2018

On Coresets for Logistic Regression.
CoRR, 2018

Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.
CoRR, 2018

Improved Algorithms for Adaptive Compressed Sensing.
CoRR, 2018

Data Streams with Bounded Deletions.
CoRR, 2018

Revisiting Frequency Moment Estimation in Random Order Streams.
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

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

Sketching for Kronecker Product Regression and P-splines.
CoRR, 2017

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

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

Near Optimal Sketching of Low-Rank Tensor Regression.
CoRR, 2017

On Low-Risk Heavy Hitters and Sparse Recovery Schemes.
CoRR, 2017

Relative Error Tensor Low Rank Approximation.
CoRR, 2017

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

Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices.
CoRR, 2017

Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness.
CoRR, 2017

Embeddings of Schatten Norms with Applications to Data Streams.
CoRR, 2017

Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams.
CoRR, 2017

Algorithms for $\ell_p$ Low Rank Approximation.
CoRR, 2017

Communication-Optimal Distributed Clustering.
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

Adaptive Matrix Vector Product.
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

Distributed Low Rank Approximation of Implicit Functions of a Matrix.
CoRR, 2016

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

Low Rank Approximation with Entrywise ℓ1-Norm Error.
CoRR, 2016

On Approximating Functions of the Singular Values in a Stream.
CoRR, 2016

How to Fake Multiply by a Gaussian Matrix.
CoRR, 2016

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

BPTree: an ℓ2 heavy hitters algorithm using constant memory.
CoRR, 2016

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

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

Faster Kernel Ridge Regression Using Sketching and Preconditioning.
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

On Sketching Quadratic Forms.
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

Frequent Directions : Simple and Deterministic Matrix Sketching.
CoRR, 2015

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

Optimal approximate matrix product in terms of stable rank.
CoRR, 2015

Input Sparsity and Hardness for Robust Subspace Approximation.
CoRR, 2015

Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality.
CoRR, 2015

Beating CountSketch for Heavy Hitters in Insertion Streams.
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

On Sketching Quadratic Forms.
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

The Simultaneous Communication of Disjointness with Applications to Data Streams.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Amplification of One-Way Information Complexity via Codes and Noise Sensitivity.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 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

Sketching as a Tool for Numerical Linear Algebra.
CoRR, 2014

On The Communication Complexity of Linear Algebraic Problems in the Message Passing Model.
CoRR, 2014

A Sketching Algorithm for Spectral Graph Sparsification.
CoRR, 2014

Optimal CUR Matrix Decompositions.
CoRR, 2014

Improved Distributed Principal Component Analysis.
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

Optimal CUR matrix decompositions.
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

Certifying Equality With Limited Interaction.
Proceedings of the Approximation, 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

When Distributed Computation Is Communication Expensive.
Proceedings of the Distributed Computing - 27th International Symposium, 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

The Fast Cauchy Transform and Faster Robust Linear Regression.
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.
Journal of Machine Learning Research, 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

How Robust are Linear Sketches to Adaptive Inputs?
CoRR, 2012

Low Rank Approximation and Regression in Input Sparsity Time
CoRR, 2012

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

On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation
CoRR, 2012

Lower Bounds for Adaptive Sparse Recovery
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

Space-efficient estimation of statistics over sub-sampled 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

Fast approximation of matrix coherence and statistical leverage.
Proceedings of the 29th International Conference on Machine Learning, 2012

A General Method for Estimating Correlated Aggregates over a Data Stream.
Proceedings of the IEEE 28th International Conference on Data Engineering (ICDE 2012), 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
Tight Bounds for Distributed Functional Monitoring
CoRR, 2011

(1+eps)-approximate Sparse Recovery
CoRR, 2011

On the Power of Adaptivity in Sparse Recovery
CoRR, 2011

Fast approximation of matrix coherence and statistical leverage
CoRR, 2011

Lower Bounds for Sparse Recovery
CoRR, 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

Steiner Transitive-Closure Spanners of Low-Dimensional Posets.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 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

Sublinear Optimization for Machine Learning
CoRR, 2010

Fast Moment Estimation in Data Streams in Optimal Space
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

Additive Spanners in Nearly Quadratic Time.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Sublinear Optimization for Machine Learning.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field.
Proceedings of the Approximation, 2010

Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners.
Proceedings of the Approximation, 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

Transitive-closure spanners.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Transitive-Closure Spanners
CoRR, 2008

Epistemic privacy.
Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 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

A Geometric Approach to Information-Theoretic Private Information Retrieval.
SIAM J. Comput., 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

Revisiting the Efficiency of Malicious Two-Party Computation.
Proceedings of the Advances in Cryptology, 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

Polylogarithmic Private Approximations and Efficient Matching.
Proceedings of the Theory of Cryptography, Third Theory of Cryptography Conference, 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

Fast Algorithms for the Free Riders Problem in Broadcast Encryption.
Proceedings of the Advances in Cryptology, 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

Practical Cryptography in High Dimensional Tori.
Proceedings of the Advances in Cryptology, 2005

A Geometric Approach to Information-Theoretic Private Information Retrieval.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 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

Private inference control.
Proceedings of the 11th ACM Conference on Computer and Communications Security, 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


  Loading...