David P. Woodruff

Available identifiers

zbMath Open woodruff.david-pWikidataQ57986254 ScholiaQ57986254MaRDI QIDQ343862

List of research outcomes

Publication	Date of Publication	Type
https://portal.mardi4nfdi.de/entity/Q6126241	2024-04-09	Paper
https://portal.mardi4nfdi.de/entity/Q6126334	2024-04-09	Paper
https://portal.mardi4nfdi.de/entity/Q6138070	2024-01-16	Paper
https://portal.mardi4nfdi.de/entity/Q6147283	2024-01-15	Paper
On differential privacy and adaptive data analysis with bounded space	2023-12-12	Paper
Low-rank approximation with 1/𝜖 1/3 matrix-vector products	2023-12-08	Paper
Memory bounds for the experts problem	2023-12-08	Paper
The Product of Gaussian Matrices is Close to Gaussian	2023-11-20	Paper
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.	2023-10-31	Paper
Tight Bounds for ℓ 1 Oblivious Subspace Embeddings	2023-10-31	Paper
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems	2023-10-31	Paper
Streaming Complexity of SVMs	2023-10-31	Paper
Towards Optimal Moment Estimation in Streaming and Distributed Models	2023-10-23	Paper
https://portal.mardi4nfdi.de/entity/Q6115400	2023-07-12	Paper
https://portal.mardi4nfdi.de/entity/Q5875452	2023-02-03	Paper
Towards Optimal Moment Estimation in Streaming and Distributed Models	2023-02-03	Paper
https://portal.mardi4nfdi.de/entity/Q5875784	2023-02-03	Paper
Pseudo-Deterministic Streaming.	2023-02-03	Paper
A fast, provably accurate approximation algorithm for sparse principal component analysis reveals human genetic variation across the world	2022-08-30	Paper
https://portal.mardi4nfdi.de/entity/Q5091167	2022-07-21	Paper
Querying a Matrix Through Matrix-Vector Products.	2022-07-21	Paper
https://portal.mardi4nfdi.de/entity/Q5091258	2022-07-21	Paper
https://portal.mardi4nfdi.de/entity/Q5088943	2022-07-18	Paper
High-Dimensional Geometric Streaming in Polynomial Space	2022-04-07	Paper
A Framework for Adversarially Robust Streaming Algorithms	2022-03-31	Paper
Querying a Matrix through Matrix-Vector Products	2022-02-22	Paper
Tight Bounds for the Subspace Sketch Problem with Applications	2021-08-06	Paper
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.	2021-08-04	Paper
https://portal.mardi4nfdi.de/entity/Q5009507	2021-08-04	Paper
On Low-Risk Heavy Hitters and Sparse Recovery Schemes	2021-08-04	Paper
Sharper Bounds for Regularized Data Fitting	2021-07-28	Paper
https://portal.mardi4nfdi.de/entity/Q5002695	2021-07-28	Paper
High Probability Frequency Moment Sketches	2021-07-28	Paper
Improved Algorithms for Adaptive Compressed Sensing	2021-07-28	Paper
https://portal.mardi4nfdi.de/entity/Q4993268	2021-06-15	Paper
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness	2021-06-15	Paper
Perfect $L_p$ Sampling in a Data Stream	2021-04-14	Paper
Oblivious Sketching of High-Degree Polynomial Kernels	2021-02-02	Paper
Tight Bounds for the Subspace Sketch Problem with Applications	2021-02-02	Paper
The Communication Complexity of Optimization	2021-02-02	Paper
Non-adaptive adaptive sampling on turnstile streams	2021-01-19	Paper
Hutch++: Optimal Stochastic Trace Estimation	2020-10-19	Paper
https://portal.mardi4nfdi.de/entity/Q5111390	2020-05-27	Paper
Embeddings of Schatten Norms with Applications to Data Streams	2020-05-27	Paper
https://portal.mardi4nfdi.de/entity/Q5214187	2020-02-07	Paper
On Approximating Matrix Norms in Data Streams	2019-11-21	Paper
Testing Matrix Rank, Optimally	2019-10-15	Paper
A PTAS for ℓp-Low Rank Approximation	2019-10-15	Paper
Tight Bounds for ℓp Oblivious Subspace Embeddings	2019-10-15	Paper
Relative Error Tensor Low Rank Approximation	2019-10-15	Paper
The Query Complexity of Mastermind with $\ell_p$ Distances	2019-09-23	Paper
https://portal.mardi4nfdi.de/entity/Q4967174	2019-07-03	Paper
An Optimal Lower Bound for Distinct Elements in the Message Passing Model	2019-06-20	Paper
On Sketching Matrix Norms and the Top Singular Vector	2019-06-20	Paper
Lower Bounds for Adaptive Sparse Recovery	2019-05-15	Paper
Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching	2019-05-15	Paper
The Fast Cauchy Transform and Faster Robust Linear Regression	2019-05-15	Paper
https://portal.mardi4nfdi.de/entity/Q4633906	2019-05-06	Paper
An Optimal Algorithm for ℓ 1 -Heavy Hitters in Insertion Streams and Related Problems	2019-03-28	Paper
Low-Rank Approximation and Regression in Input Sparsity Time	2018-08-02	Paper
Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching	2018-07-16	Paper
Adaptive Matrix Vector Product	2018-07-16	Paper
Low-Rank PSD Approximation in Input-Sparsity Time	2018-07-16	Paper
https://portal.mardi4nfdi.de/entity/Q4636472	2018-04-19	Paper
https://portal.mardi4nfdi.de/entity/Q4606301	2018-03-02	Paper
When distributed computation is communication expensive	2018-01-17	Paper
Optimal Approximate Matrix Product in Terms of Stable Rank	2017-12-19	Paper
Faster Kernel Ridge Regression Using Sketching and Preconditioning	2017-11-06	Paper
https://portal.mardi4nfdi.de/entity/Q5368755	2017-10-10	Paper
Sketching for M-Estimators: A Unified Approach to Robust Regression	2017-10-05	Paper
Optimal principal component analysis in distributed and streaming models	2017-09-29	Paper
Weighted low rank approximations with provable guarantees	2017-09-29	Paper
On approximating functions of the singular values in a stream	2017-09-29	Paper
Beating CountSketch for heavy hitters in insertion streams	2017-09-29	Paper
Communication lower bounds for statistical estimation problems via a distributed data processing inequality	2017-09-29	Paper
https://portal.mardi4nfdi.de/entity/Q5365016	2017-09-29	Paper
Tight Bounds for Graph Problems in Insertion Streams	2017-08-31	Paper
Low rank approximation with entrywise l 1 -norm error	2017-08-17	Paper
New Algorithms for Heavy Hitters in Data Streams (Invited Talk)	2017-07-14	Paper
Certifying Equality With Limited Interaction.	2017-03-22	Paper
Optimal CUR Matrix Decompositions	2017-03-10	Paper
How does your crystal grow? A commentary on Burton, Cabrera and Frank (1951) ‘The growth of crystals and the equilibrium structure of their surfaces’	2017-01-13	Paper
Certifying equality with limited interaction	2016-11-29	Paper
Frequent Directions: Simple and Deterministic Matrix Sketching	2016-09-23	Paper
The Fast Cauchy Transform and Faster Robust Linear Regression	2016-06-16	Paper
On Sketching Quadratic Forms	2016-04-15	Paper
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity	2015-10-27	Paper
The Simultaneous Communication of Disjointness with Applications to Data Streams	2015-10-27	Paper
A general method for estimating correlated aggregates over a data stream	2015-10-19	Paper
Beyond set disjointness	2015-09-03	Paper
Spanners and sparsifiers in dynamic streams	2015-09-03	Paper
https://portal.mardi4nfdi.de/entity/Q5501255	2015-08-03	Paper
Optimal CUR Matrix Decompositions	2015-06-26	Paper
Turnstile streaming algorithms might as well be linear sketches	2015-06-26	Paper
Numerical linear algebra in the streaming model	2015-02-04	Paper
Computational Advertising: Techniques for Targeting Relevant Ads	2015-01-22	Paper
https://portal.mardi4nfdi.de/entity/Q2934612	2014-12-18	Paper
Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error	2014-12-05	Paper
When distributed computation is communication expensive	2014-09-29	Paper
Steiner transitive-closure spanners of low-dimensional posets	2014-08-14	Paper
How robust are linear sketches to adaptive inputs?	2014-08-07	Paper
Low-Rank Approximation and Regression in Input Sparsity Time	2014-08-07	Paper
On the Power of Adaptivity in Sparse Recovery	2014-07-30	Paper
(1 + eps)-Approximate Sparse Recovery	2014-07-30	Paper
Efficient Sketches for Earth-Mover Distance, with Applications	2014-07-25	Paper
The Data Stream Space Complexity of Cascaded Norms	2014-07-25	Paper
Near-optimal private approximation protocols via a black box transformation	2014-06-05	Paper
Fast moment estimation in data streams in optimal space	2014-06-05	Paper
Subspace embeddings for the L 1 -norm with applications	2014-06-05	Paper
https://portal.mardi4nfdi.de/entity/Q5417655	2014-05-22	Paper
https://portal.mardi4nfdi.de/entity/Q5417696	2014-05-22	Paper
https://portal.mardi4nfdi.de/entity/Q5417697	2014-05-22	Paper
Lower Bounds for Sparse Recovery	2014-05-22	Paper
Tight bounds for distributed functional monitoring	2014-05-13	Paper
https://portal.mardi4nfdi.de/entity/Q5405231	2014-04-01	Paper
On deterministic sketching and streaming for sparse recovery and norm estimation	2014-03-03	Paper
Sublinear optimization for machine learning	2014-02-17	Paper
A quadratic lower bound for three-query linear locally decodable codes over any field	2014-02-11	Paper
A Tight Lower Bound for High Frequency Moment Estimation with Small Error	2013-10-04	Paper
Transitive-Closure Spanners	2013-03-19	Paper
On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation	2012-11-02	Paper
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners	2012-09-12	Paper
Optimal Random Sampling from Distributed Streams Revisited	2011-10-28	Paper
Tolerant Algorithms	2011-09-16	Paper
Streaming Algorithms with One-Sided Estimation	2011-08-17	Paper
Steiner Transitive-Closure Spanners of Low-Dimensional Posets	2011-07-06	Paper
Epistemic privacy	2011-05-16	Paper
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners	2010-09-10	Paper
A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field	2010-09-10	Paper
Additive Spanners in Nearly Quadratic Time	2010-09-07	Paper
Optimal approximations of the frequency moments of data streams	2010-08-16	Paper
Corruption and Recovery-Efficient Locally Decodable Codes	2008-11-27	Paper
A Geometric Approach to Information-Theoretic Private Information Retrieval	2008-08-14	Paper
Practical Cryptography in High Dimensional Tori	2008-05-06	Paper
Revisiting the Efficiency of Malicious Two-Party Computation	2007-11-29	Paper
Fast Algorithms for the Free Riders Problem in Broadcast Encryption	2007-09-04	Paper
Better Approximations for the Minimum Common Integer Partition Problem	2007-08-28	Paper
Theory of Cryptography	2007-02-12	Paper
Advances in Cryptology – CRYPTO 2004	2005-08-23	Paper
https://portal.mardi4nfdi.de/entity/Q4737241	2004-08-11	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: David P. Woodruff