David P. Woodruff

David P. Woodruff's AcademicInfluence.com Rankings

David P. Woodruff

Computer Science

#5519

World Rank

#5829

Historical Rank

Numerical Analysis

#26

World Rank

#28

Historical Rank

Database

#2676

World Rank

#2798

Historical Rank

computer-science Degrees

Download Badge

Computer Science

David P. Woodruff's Degrees

PhD Computer Science Stanford University
Masters Computer Science Stanford University
Bachelors Computer Science Stanford University

Similar Degrees You Can Earn

Why Is David P. Woodruff Influential?

(Suggest an Edit or Addition)

(See a Problem?)

David P. Woodruff's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Sketching as a Tool for Numerical Linear Algebra (2014) (940)
Low-Rank Approximation and Regression in Input Sparsity Time (2012) (554)
Fast approximation of matrix coherence and statistical leverage (2011) (460)
Numerical linear algebra in the streaming model (2009) (341)
An optimal algorithm for the distinct elements problem (2010) (320)
Optimal approximations of the frequency moments of data streams (2005) (263)
Lower bounds for sparse recovery (2010) (192)
Optimal space lower bounds for all frequency moments (2004) (179)
On the exact space complexity of sketching and streaming small norms (2010) (160)
Low rank approximation and regression in input sparsity time (2013) (155)
Tight lower bounds for the distinct elements problem (2003) (152)
Optimal CUR matrix decompositions (2014) (149)
Communication lower bounds for statistical estimation problems via a distributed data processing inequality (2015) (147)
Improved Distributed Principal Component Analysis (2014) (136)
Frequent Directions: Simple and Deterministic Matrix Sketching (2015) (135)
1-pass relative-error Lp-sampling with applications (2010) (123)
Sublinear Optimization for Machine Learning (2010) (123)
Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error (2011) (114)
Optimal Approximate Matrix Product in Terms of Stable Rank (2015) (112)
Tight bounds for distributed functional monitoring (2011) (101)
Optimal principal component analysis in distributed and streaming models (2015) (98)
Turnstile streaming algorithms might as well be linear sketches (2014) (97)
Faster Kernel Ridge Regression Using Sketching and Preconditioning (2016) (96)
A geometric approach to information-theoretic private information retrieval (2005) (96)
The Fast Cauchy Transform and Faster Robust Linear Regression (2012) (94)
Polylogarithmic Private Approximations and Efficient Matching (2006) (93)
Fast moment estimation in data streams in optimal space (2010) (92)
Transitive-Closure Spanners (2008) (92)
Subspace Embeddings for the Polynomial Kernel (2014) (88)
New Lower Bounds for General Locally Decodable Codes (2007) (88)
Relative Error Tensor Low Rank Approximation (2017) (86)
Coresets and sketches for high dimensional subspace approximation problems (2010) (85)
Low rank approximation with entrywise l1-norm error (2017) (82)
Weighted low rank approximations with provable guarantees (2016) (80)
Principal Component Analysis and Higher Correlations for Distributed Data (2013) (79)
On Coresets for Logistic Regression (2018) (77)
When distributed computation is communication expensive (2013) (76)
Subspace embeddings for the L1-norm with applications (2011) (74)
On the Power of Adaptivity in Sparse Recovery (2011) (74)
Lower Bounds for Additive Spanners, Emulators, and More (2006) (71)
Subspace Embeddings and $\ell_p$-Regression Using Exponential Random Variables (2013) (70)
Input Sparsity and Hardness for Robust Subspace Approximation (2015) (68)
Efficient Sketches for Earth-Mover Distance, with Applications (2009) (68)
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension (2018) (67)
Spanners and sparsifiers in dynamic streams (2014) (63)
BPTree: An ℓ2 Heavy Hitters Algorithm Using Constant Memory (2016) (60)
The Data Stream Space Complexity of Cascaded Norms (2009) (60)
On Sketching Quadratic Forms (2015) (58)
Hutch++: Optimal Stochastic Trace Estimation (2020) (58)
Oblivious Sketching of High-Degree Polynomial Kernels (2019) (56)
A Framework for Adversarially Robust Streaming Algorithms (2020) (55)
On Sketching Matrix Norms and the Top Singular Vector (2014) (54)
Low Rank Approximation with Entrywise ℓ1-Norm Error (2016) (54)
Sketching for M-Estimators: A Unified Approach to Robust Regression (2015) (54)
Additive Spanners in Nearly Quadratic Time (2010) (52)
Learning Two Layer Rectified Neural Networks in Polynomial Time (2018) (52)
Revisiting the Efficiency of Malicious Two-Party Computation (2007) (52)
Sharper Bounds for Regularized Data Fitting (2016) (52)
Faster Algorithms for High-Dimensional Robust Covariance Estimation (2019) (51)
The communication and streaming complexity of computing the longest common and increasing subsequences (2007) (47)
Practical Cryptography in High Dimensional Tori (2005) (47)
Optimal Random Sampling from Distributed Streams Revisited (2011) (46)
How robust are linear sketches to adaptive inputs? (2012) (44)
A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field (2010) (44)
Sketching for Kronecker Product Regression and P-splines (2017) (44)
(1 + eps)-Approximate Sparse Recovery (2011) (43)
Beating CountSketch for heavy hitters in insertion streams (2015) (42)
Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices (2017) (41)
On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation (2012) (39)
An Optimal Lower Bound for Distinct Elements in the Message Passing Model (2014) (39)
Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams (2017) (39)
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners (2010) (38)
New Characterizations in Turnstile Streams with Applications (2016) (37)
Sublinear Time Orthogonal Tensor Decomposition (2016) (37)
A Tight Lower Bound for High Frequency Moment Estimation with Small Error (2013) (37)
Efficient and Thrifty Voting by Any Means Necessary (2019) (37)
Communication-Optimal Distributed Clustering (2016) (37)
Algorithms for ℓp Low Rank Approximation (2017) (36)
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators (2020) (36)
A PTAS for 𝓁p-Low Rank Approximation (2019) (35)
Is min-wise hashing optimal for summarizing set intersection? (2014) (35)
Fast Manhattan sketches in data streams (2010) (34)
Perfect Lp Sampling in a Data Stream (2018) (34)
Communication Efficient Distributed Kernel Principal Component Analysis (2015) (34)
Near Optimal Linear Algebra in the Online and Sliding Window Models (2018) (34)
Sketching algorithms for genomic data analysis and querying in a secure enclave (2018) (34)
Asymptotically Optimal Communication for Torus-Based Cryptography (2004) (33)
On approximating functions of the singular values in a stream (2016) (32)
Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching (2013) (32)
Low Rank Approximation Lower Bounds in Row-Update Streams (2014) (32)
Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond (2015) (31)
Sample-Optimal Low-Rank Approximation of Distance Matrices (2019) (31)
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness (2017) (30)
Applications of the Shannon-Hartley theorem to data streams and sparse recovery (2012) (30)
Private inference control (2004) (30)
Efficient and private distance approximation in the communication and streaming models (2007) (30)
Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors (2016) (30)
Learning-Augmented Data Stream Algorithms (2020) (29)
Optimal Communication-Distortion Tradeoff in Voting (2020) (29)
Tight Bounds for Graph Problems in Insertion Streams (2015) (29)
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings (2022) (28)
Querying a Matrix through Matrix-Vector Products (2019) (28)
Sublinear Time Low-Rank Approximation of Distance Matrices (2018) (28)
Dimensionality Reduction for Tukey Regression (2019) (28)
Beyond set disjointness: the communication complexity of finding the intersection (2014) (27)
Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error (2011) (27)
Space-Efficient Estimation of Statistics Over Sub-Sampled Streams (2012) (26)
The Communication Complexity of Optimization (2019) (26)
Multi-Tuple Deletion Propagation: Approximations and Complexity (2013) (26)
An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems (2016) (26)
Low-Rank PSD Approximation in Input-Sparsity Time (2017) (26)
Tight Bounds for ℓ1 Oblivious Subspace Embeddings (2019) (25)
Low Rank Approximation with Entrywise $\ell_1$-Norm Error (2016) (24)
A General Method for Estimating Correlated Aggregates Over a Data Stream (2012) (24)
Near Optimal Sketching of Low-Rank Tensor Regression (2017) (23)
Optimal Sketching for Kronecker Product Regression and Low Rank Approximation (2019) (23)
Lower Bounds for Adaptive Sparse Recovery (2012) (23)
The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication (2015) (23)
The average-case complexity of counting distinct elements (2009) (23)
Towards a Zero-One Law for Column Subset Selection (2018) (22)
Distributed low rank approximation of implicit functions of a matrix (2016) (22)
Fast Sketching of Polynomial Kernels of Polynomial Degree (2021) (21)
Open Problems in Data Streams, Property Testing, and Related Topics (2011) (21)
Optimal Approximations of the Frequency Moments (2004) (21)
Sketching Structured Matrices for Faster Nonlinear Regression (2013) (21)
New Algorithms for Heavy Hitters in Data Streams (Invited Talk) (2016) (20)
The Simultaneous Communication of Disjointness with Applications to Data Streams (2015) (20)
Testing Matrix Rank, Optimally (2018) (20)
Faster Algorithms for Binary Matrix Factorization (2019) (20)
The Complexity of Linear Dependence Problems in Vector Spaces (2011) (20)
( 1 + )-approximate Sparse Recovery (2011) (19)
Matrix Completion and Related Problems via Strong Duality (2017) (19)
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems (2020) (19)
Tolerant Algorithms (2011) (19)
Epistemic privacy (2008) (19)
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows (2018) (19)
Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling (2020) (18)
Average Case Column Subset Selection for Entrywise 퓁1-Norm Loss (2019) (18)
Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching (2015) (17)
Efficient Sketches for EarthMover Distance , with Applications (2009) (17)
An Empirical Evaluation of Sketching for Numerical Linear Algebra (2018) (17)
A Simple Message-Optimal Algorithm for Random Sampling from a Distributed Stream (2016) (17)
Algorithms for $\ell_p$ Low-Rank Approximation (2017) (17)
On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model (2014) (17)
Embeddings of Schatten Norms with Applications to Data Streams (2017) (17)
Rectangle-efficient aggregation in spatial data streams (2012) (17)
Improved Algorithms for Adaptive Compressed Sensing (2018) (17)
Revisiting Norm Estimation in Data Streams (2008) (16)
How to Reduce Dimension With PCA and Random Projections? (2020) (16)
High Probability Frequency Moment Sketches (2018) (16)
Robust and Sample Optimal Algorithms for PSD Low Rank Approximation (2019) (16)
Weighted Reservoir Sampling from Distributed Streams (2019) (16)
Certifying Equality With Limited Interaction (2016) (16)
Clustering via matrix powering (2004) (16)
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra (2020) (16)
How to Fake Multiply by a Gaussian Matrix (2016) (16)
Communication-optimal Distributed Principal Component Analysis in the Column-partition Model (2015) (15)
Data Streams with Bounded Deletions (2018) (15)
Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? (2017) (15)
Tight Bounds for the Subspace Sketch Problem with Applications (2019) (15)
Reusable low-error compressive sampling schemes through privacy (2012) (14)
Non-adaptive adaptive sampling on turnstile streams (2020) (14)
BPTree: an $\ell_2$ heavy hitters algorithm using constant memory (2016) (14)
Distributed Kernel Principal Component Analysis (2015) (14)
Fast Regression with an `∞ Guarantee∗ (2017) (14)
Sublinear Time Numerical Linear Algebra for Structured Matrices (2019) (14)
Tight Dimensionality Reduction for Sketching Low Degree Polynomial Kernels (2019) (12)
Sharper Bounds for Regression and Low-Rank Approximation with Regularization (2016) (12)
The Coin Problem with Applications to Data Streams (2020) (12)
Stochastic Streams: Sample Complexity vs. Space Complexity (2016) (12)
Transitive-Closure Spanners of the Hypercube and the Hypergrid (2009) (12)
Steiner transitive-closure spanners of low-dimensional posets (2010) (12)
Towards a Zero-One Law for Entrywise Low Rank Approximation (2018) (11)
The Sketching Complexity of Graph Cuts (2014) (11)
A simple proof of a new set disjointness with applications to data streams (2021) (11)
An Optimal Algorithm for ℓ1-Heavy Hitters in Insertion Streams and Related Problems (2018) (11)
Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order (2016) (11)
Towards Optimal Moment Estimation in Streaming and Distributed Models (2019) (11)
Corruption and Recovery-Efficient Locally Decodable Codes (2008) (10)
Graph Spanners in the Message-Passing Model (2019) (10)
Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski p-Norms (2018) (10)
Improved testing of low rank matrices (2014) (10)
The One-Way Communication Complexity of Dynamic Time Warping Distance (2019) (10)
On Low-Risk Heavy Hitters and Sparse Recovery Schemes (2017) (10)
Better Approximations for the Minimum Common Integer Partition Problem (2006) (9)
Fast Algorithms for the Free Riders Problem in Broadcast Encryption (2006) (9)
On Sketching the q to p norms (2018) (9)
Regularized Weighted Low Rank Approximation (2019) (9)
Revisiting Frequency Moment Estimation in Random Order Streams (2018) (9)
Approximation Algorithms for ࡁ0-Low Rank Approximation (2017) (9)
Distributed Statistical Estimation of Matrix Products with Applications (2018) (8)
Optimal Sample Complexity for Matrix Completion and Related Problems via 𝓁s2-Regularization (2017) (8)
Total Least Squares Regression in Input Sparsity Time (2019) (8)
Input-Sparsity Low Rank Approximation in Schatten Norm (2020) (8)
Tight Bounds for $\ell_p$ Oblivious Subspace Embeddings (2018) (8)
Oblivious Sketching for Logistic Regression (2021) (8)
Epistemic privacy (2010) (8)
Explicit Exclusive Set Systems with Applications to Broadcast Encryption (2006) (8)
Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time (2021) (8)
Learning-Augmented k-means Clustering (2021) (7)
Optimal Sketching for Trace Estimation (2021) (7)
Learning the Positions in CountSketch (2020) (7)
Approximation Algorithms for l0-Low Rank Approximation (2017) (7)
On Approximating Matrix Norms in Data Streams (2019) (7)
True Randomness from Big Data (2016) (7)
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity (2015) (6)
Fast Regression with an $\ell_\infty$ Guarantee (2017) (6)
Dimensionality Reduction for the Sum-of-Distances Metric (2019) (6)
Triangle and Four Cycle Counting with Predictions in Graph Streams (2022) (6)
Frequency Moments (2009) (6)
Learning a Latent Simplex in Input-Sparsity Time (2021) (6)
Low-rank approximation with 1/𝜖1/3 matrix-vector products (2022) (6)
Memory bounds for the experts problem (2022) (6)
When Distributed Computation does not Help (2013) (6)
Strong Coresets for Subspace Approximation and k-Median in Nearly Linear Time (2019) (6)
Optimal Deterministic Coresets for Ridge Regression (2020) (6)
The White-Box Adversarial Data Stream Model (2022) (6)
Exponentially Improved Dimensionality Reduction for 𝓁1: Subspace Embeddings and Independence Testing (2021) (5)
A Near-Optimal Algorithm for L1-Difference (2009) (5)
Near-optimal private approximation protocols via a black box transformation (2011) (5)
LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew (2020) (5)
Cryptography in an Unbounded Computational Model (2002) (5)
Bounding the Width of Neural Networks via Coupled Initialization - A Worst Case Analysis (2022) (5)
Numerical Linear Algebra in the Sliding Window Model (2018) (5)
Robust Subspace Approximation in a Stream (2018) (5)
High-Dimensional Geometric Streaming in Polynomial Space (2022) (4)
Span Recovery for Deep Neural Networks with Applications to Input Obfuscation (2020) (4)
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes (2020) (4)
In-Database Regression in Input Sparsity Time (2021) (4)
Optimal 𝓁1 Column Subset Selection and a Fast PTAS for Low Rank Approximation (2021) (4)
Truly Perfect Samplers for Data Streams and Sliding Windows (2021) (4)
Few-Shot Data-Driven Algorithms for Low Rank Approximation (2021) (4)
Average-Case Communication Complexity of Statistical Problems (2021) (4)
WOR and p's: Sketches for 𝓁p-Sampling Without Replacement (2020) (4)
Active Sampling for Linear Regression Beyond the $\ell_2$ Norm (2021) (4)
Pseudo-deterministic Streaming (2019) (4)
Streaming Complexity of SVMs (2020) (4)
Fast Regression for Structured Inputs (2022) (4)
The Fast Cauchy Transform: with Applications to Basis Construction, Regression, and Subspace Approximation in L1 (2012) (4)
Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel k-means Clustering (2019) (4)
Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation (2020) (4)
Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams (2019) (3)
Active Linear Regression for $\ell_p$ Norms and Beyond (2021) (3)
Learning Augmented Binary Search Trees (2022) (3)
Approximation Algorithms for Sparse Principal Component Analysis (2020) (3)
Streaming Algorithms with One-Sided Estimation (2011) (3)
Testing Positive Semidefiniteness Using Linear Measurements (2022) (3)
Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time (2022) (3)
Data Streams and Applications in Computer Science (2014) (3)
Robust Communication-Optimal Distributed Clustering Algorithms (2017) (3)
Editorial to the Special Issue on SODA'12 (2016) (3)
Online Lewis Weight Sampling (2022) (3)
On Differential Privacy and Adaptive Data Analysis with Bounded Space (2023) (3)
A Very Sketchy Talk (Invited Talk) (2021) (2)
On Learned Sketches for Randomized Numerical Linear Algebra (2020) (2)
A PTAS for l p-Low Rank Approximation (2018) (2)
Separations for Estimating Large Frequency Moments on Data Streams (2021) (2)
Distinct Elements is Hard Even for Random Data Streams (2008) (2)
Approximation Algorithms for l 0 -Low Rank Approximation. (2017) (2)
Subspace Exploration: Bounds on Projected Frequency Estimation (2021) (2)
Improved Algorithms for Low Rank Approximation from Sparsity (2021) (2)
On the Communication Complexity of Distributed Set-Joins (2015) (2)
Steiner transitive-closure spanners of low-dimensional posets (2010) (2)
Optimal Query Complexities for Dynamic Trace Estimation (2022) (2)
Streaming Algorithms for Learning with Experts: Deterministic Versus Robust (2023) (2)
Sketching Algorithms and Lower Bounds for Ridge Regression (2022) (2)
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams (2019) (2)
Streaming and Distributed Algorithms for Robust Column Subset Selection (2021) (1)
ICALP 2022 - 49th EATCS International Colloquium on Automata, Languages and Programming (2021) (1)
D S ] 6 A pr 2 01 8 Tight Bounds for l p Oblivious Subspace Embeddings (2018) (1)
A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World (2022) (1)
Conditional Sparse 𝓁p-norm Regression With Optimal Probability (2018) (1)
Learning-Augmented Sketches for Hessians (2021) (1)
Optimal Sketching Bounds for Sparse Linear Regression (2023) (1)
Low-Rank Approximation from Communication Complexity (2019) (1)
Robust Algorithms on Adaptive Inputs from Bounded Adversaries (2023) (1)
Certifying Equality With Limited Interaction (2016) (1)
Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss (2020) (1)
`p-SAMPLING WITHOUT REPLACEMENT (2020) (1)
Theory and Applications of Hashing (Dagstuhl Seminar 17181) (2017) (1)
Noisy Boolean Hidden Matching with Applications (2021) (1)
Automatic Differentiation of Sketched Regression (2020) (1)
The Product of Gaussian Matrices is Close to Gaussian (2021) (1)
When distributed computation is communication expensive (2014) (1)
Advances in Cryptology – EUROCRYPT 2019 (2019) (1)
Conditional Sparse $\ell_p$-norm Regression With Optimal Probability (2018) (1)
Reduced-Rank Regression with Operator Norm Error (2020) (1)
Near-Linear Sample Complexity for Lp Polynomial Regression (2022) (1)
Guest Editorial for Information Complexity and Applications (2016) (1)
The Query Complexity of Mastermind with lp Distances (2019) (1)
A Framework for Adversarially Robust Streaming Algorithms (2021) (1)
A Very Sketchy Talk (2021) (1)
A PTAS for $\ell_p$-Low Rank Approximation (2018) (1)
A Framework for Adversarially Robust Streaming Algorithms (2022) (1)
A Sketching Algorithm for Spectral Graph Sparsification (2014) (1)
Frequency Estimation with One-Sided Error (2021) (1)
Approximation Algorithms for $\ell_0$-Low Rank Approximation (2017) (0)
WOR and $p$'s: Sketches for $\ell_p$-Sampling Without Replacement (2020) (0)
The Information Complexity of Equality and Finding the Intersection (2013) (0)
An Efficient Semi-Streaming PTAS for Tournament Feedback ArcSet with Few Passes (2021) (0)
Report from Dagstuhl Seminar 17181 Theory and Applications of Hashing (2017) (0)
Theory and applications of hashing : report from Dagstuhl Seminar 17181 (2017) (0)
Optimal Eigenvalue Approximation via Sketching (2023) (0)
The Round Complexity of Small Set Intersection (2013) (0)
DICTIONS IN GRAPH STREAMS (2022) (0)
Technical Perspective (2022) (0)
A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field (2012) (0)
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online (2023) (0)
Model Counting Meets Distinct Elements in a Data Stream (2022) (0)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products (2022) (0)
Total Least Squares Regression in Input Sparsity Time ∗ Huaian (2019) (0)
Optimal Approximations of the Frequency Moments Piotr Indyk MIT (2004) (0)
Sketching and Streaming Matrix Norms (2017) (0)
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions (2022) (0)
Lecture 17: Pseudorandom Generators Based on Scribe Notes (2007) (0)
Optimal $\ell_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation (2020) (0)
CS 15-859 : Algorithms for Big Data Fall 2017 Lecture 10 — Nov (2017) (0)
Sketching for Geometric Problems (2017) (0)
Recovery from Non-Decomposable Distance Oracles (2022) (0)
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming (2023) (0)
Arnab BhattacharyyaElena GrigorescuKyomin JungSofya Raskhodnikova (2009) (0)
X Primal Problem ( 1 ) Bi-Dual Problem ( 2 ) Strong Duality By Theorem 3 . 3 + Dual Certificate Surface of ( 1 ) Surface of ( 2 ) Common Optimal Solution AB (2017) (0)
Active Linear Regression for ℓp Norms and Beyond (2022) (0)
Introduction to the Special Issue on SODA’18 (2019) (0)
2 Decoding with Error-locating Pairs (2002) (0)
Streaming Algorithms with Large Approximation Factors (2022) (0)
Adaptive Sketches for Robust Regression with Importance Sampling (2022) (0)
Guest Editorial for Information Complexity and Applications (2016) (0)
Space-Efficient Estimation of Statistics Over Sub-Sampled Streams (2015) (0)
Processing Big Data Streams (NII Shonan Meeting 2017-7) (2017) (0)
The 𝓁p-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines (2023) (0)
Adaptive Single-Pass Stochastic Gradient Descent in Input Sparsity Time (2021) (0)
2 New Characterizations in Turnstile Streams with Applications (2016) (0)
Simpler Algorithm in Gradient Descent (2020) (0)
Adaptive Matrix Vector Product (2017) (0)
Low Rank Approximation for General Tensor Networks (2022) (0)
Non-PSD Matrix Sketching with Applications to Regression and Optimization (2021) (0)
Lower Bounds for Data Streams (2014) (0)
The $\ell_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines (2022) (0)
Sketching for Geometric Problems (Invited Talk) (2017) (0)
1 Hints from Office Hours 1 . 1 Question 1 : Matrix Multiplication Runtime (2019) (0)
Almost Linear Constant-Factor Sketching for 𝓁1 and Logistic Regression (2023) (0)
19 : 2 On Low-Risk Heavy Hitters and Sparse Recovery Schemes 1 (2018) (0)
Recent Advances in Randomized Numerical Linear Algebra (NII Shonan Meeting 2016-10) (2016) (0)
Single Pass Entrywise-Transformed Low Rank Approximation (2021) (0)
Sketching algorithms for genomic data analysis and querying in a secure enclave (2020) (0)
Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters (2021) (0)

This paper list is powered by the following services:

What Schools Are Affiliated With David P. Woodruff?

David P. Woodruff is affiliated with the following schools:

David P. Woodruff's Academic­Influence.com Rankings

David P. Woodruff's Degrees

Similar Degrees You Can Earn

Why Is David P. Woodruff Influential?

David P. Woodruff's Published Works

Published Works

What Schools Are Affiliated With David P. Woodruff?

David P. Woodruff's AcademicInfluence.com Rankings