David P. Woodruff
#128,375
Most Influential Person Now
David P. Woodruff's AcademicInfluence.com Rankings
David P. Woodruffcomputer-science Degrees
Computer Science
#5519
World Rank
#5829
Historical Rank
Numerical Analysis
#26
World Rank
#28
Historical Rank
Database
#2676
World Rank
#2798
Historical Rank

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)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: