default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDDavid P. Woodruff
2020 – today
- 2025
[j43]David P. Woodruff, Shenghao Xie, Samson Zhou:
Perfect Sampling in Turnstile Streams Beyond Small Moments. Proc. ACM Manag. Data 3(2): 106:1-106:27 (2025)- [c291]Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, David P. Woodruff:
Range Counting Oracles for Geometric Problems. SoCG 2025: 42:1-42:16 - [c290]Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu, Ali Vakilian, David P. Woodruff:
Guessing Efficiently for Constrained Subspace Approximation. ICALP 2025: 29:1-29:20 - [c289]Shiyuan Feng, William Swartworth, David P. Woodruff:
Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model. ICALP 2025: 75:1-75:19 - [c288]Amit Chakrabarti, Jeffrey Jiang, David P. Woodruff, Taisuke Yasuda:
Streaming Algorithms For ℓp Flows and ℓp Regression. ICLR 2025 - [c287]Ravindran Kannan, Chiranjib Bhattacharyya, Praneeth Kacham, David P. Woodruff:
LevAttention: Time, Space and Streaming Efficient Algorithm for Heavy Attentions. ICLR 2025 - [c286]Sandeep Silwal, David P. Woodruff, Qiuyi Zhang:
Beyond Worst-Case Dimensionality Reduction for Sparse Vectors. ICLR 2025 - [c285]Matthew Ding
, Alexandro Garces, Jason Li, Honghao Lin, Jelani Nelson, Vihan Shah, David P. Woodruff:
Space Complexity of Minimum Cut Problems in Single-Pass Streams. ITCS 2025: 43:1-43:23 - [c284]William Swartworth, David P. Woodruff:
Tight Sampling Bounds for Eigenvalue Approximation. SODA 2025: 489-516 - [c283]Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou:
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness. STOC 2025: 395-406 - [i244]David P. Woodruff, Taisuke Yasuda:
John Ellipsoids via Lazy Updates. CoRR abs/2501.01801 (2025) - [i243]Zhihao Jia, Qi Pang, Trung Tran, David P. Woodruff, Zhihao Zhang, Wenting Zheng:
Communication Bounds for the Distributed Experts Problem. CoRR abs/2501.03132 (2025) - [i242]Raphael A. Meyer, William Swartworth, David P. Woodruff:
Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra. CoRR abs/2502.08029 (2025) - [i241]Sandeep Silwal, David P. Woodruff, Qiuyi Zhang:
Beyond Worst-Case Dimensionality Reduction for Sparse Vectors. CoRR abs/2502.19865 (2025) - [i240]Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou:
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness. CoRR abs/2503.19629 (2025) - [i239]David P. Woodruff, Shenghao Xie, Samson Zhou:
Perfect Sampling in Turnstile Streams Beyond Small Moments. CoRR abs/2504.07237 (2025) - [i238]Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, David P. Woodruff:
Range Counting Oracles for Geometric Problems. CoRR abs/2504.15292 (2025) - [i237]Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou:
Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings. CoRR abs/2504.16229 (2025) - [i236]Alina Ene, Alessandro Epasto, Vahab Mirrokni, Hoai-An Nguyen, Huy L. Nguyen, David P. Woodruff, Peilin Zhong:
Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures. CoRR abs/2504.18394 (2025) - [i235]Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu, Ali Vakilian, David P. Woodruff:
Guessing Efficiently for Constrained Subspace Approximation. CoRR abs/2504.20883 (2025) - [i234]Shiyuan Feng, William Swartworth, David P. Woodruff:
Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model. CoRR abs/2504.21175 (2025) - [i233]Shiyuan Feng, Ying Feng, George Z. Li, Zhao Song, David P. Woodruff, Lichen Zhang:
On Differential Privacy for Adaptively Solving Search Problems via Sketching. CoRR abs/2506.05503 (2025) - [i232]Honghao Lin, Hoai-An Nguyen, David P. Woodruff:
On Sketching Trimmed Statistics. CoRR abs/2506.07342 (2025) - [i231]Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas, David P. Woodruff, Samson Zhou:
On Fine-Grained Distinct Element Estimation. CoRR abs/2506.22608 (2025) - 2024
- [j42]Rajesh Jayaram, David P. Woodruff, Samson Zhou:
Streaming Algorithms with Few State Changes. Proc. ACM Manag. Data 2(2): 82 (2024) - [j41]Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, Jason Zhang:
Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut. Proc. ACM Manag. Data 2(2): 85 (2024) - [c282]Praneeth Kacham, David P. Woodruff:
Faster Algorithms for Schatten-p Low Rank Approximation. APPROX/RANDOM 2024: 55:1-55:19 - [c281]Aashiq Muhamed, Oscar Li, David P. Woodruff, Mona T. Diab, Virginia Smith:
GRASS: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients. EMNLP 2024: 14978-15003 - [c280]Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou:
A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches. FOCS 2024: 2318-2343 - [c279]Yi Li, Honghao Lin, David P. Woodruff:
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms. ICLR 2024 - [c278]Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, Amir Zandieh:
HyperAttention: Long-context Attention in Near-Linear Time. ICLR 2024 - [c277]Zhou Lu, Qiuyi Zhang, Xinyi Chen, Fred Zhang, David P. Woodruff, Elad Hazan:
Adaptive Regret for Bandits Made Possible: Two Queries Suffice. ICLR 2024 - [c276]Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, Michael Wunder:
Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond. ICML 2024 - [c275]Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong:
High-Dimensional Geometric Streaming for Nearly Low Rank Data. ICML 2024 - [c274]Ying Feng, Aayush Jain, David P. Woodruff:
Fast White-Box Adversarial Streaming Without a Random Oracle. ICML 2024 - [c273]Milind Prabhu, David P. Woodruff:
Learning Multiple Secrets in Mastermind. ICML 2024 - [c272]William J. Swartworth, David P. Woodruff:
Fast Sampling-Based Sketches for Tensors. ICML 2024 - [c271]David P. Woodruff, Taisuke Yasuda:
Reweighted Solutions for Weighted Low Rank Approximation. ICML 2024 - [c270]David P. Woodruff, Taisuke Yasuda:
Coresets for Multiple ℓp Regression. ICML 2024 - [c269]Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff:
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. ITCS 2024: 13:1-13:24 - [c268]Justin Y. Chen, Piotr Indyk, David P. Woodruff:
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions. ITCS 2024: 32:1-32:22 - [c267]Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang:
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions. ITCS 2024: 79:1-79:23 - [c266]Zhao Song, Ali Vakilian, David P. Woodruff, Samson Zhou:
On Socially Fair Low-Rank Approximation and Column Subset Selection. NeurIPS 2024 - [c265]Zhihao Jia, Qi Pang, Trung Tran, David P. Woodruff, Zhihao Zhang, Wenting Zheng:
Communication Bounds for the Distributed Experts Problem. NeurIPS 2024 - [c264]Praneeth Kacham, David P. Woodruff:
Approximating the Top Eigenvector in Random Order Streams. NeurIPS 2024 - [c263]Hamed Shirzad, Honghao Lin, Balaji Venkatachalam, Ameya Velingker, David P. Woodruff, Danica J. Sutherland:
Even Sparser Graph Transformers. NeurIPS 2024 - [c262]David P. Woodruff, Taisuke Yasuda:
John Ellipsoids via Lazy Updates. NeurIPS 2024 - [c261]David P. Woodruff, Samson Zhou:
Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters. NeurIPS 2024 - [c260]David P. Woodruff:
Approximation Algorithms on Matrices - With Some Database Applications! PODS Companion 2024: 5-6 - [c259]Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, Guanghao Ye:
Improving the Bit Complexity of Communication for Distributed Convex Optimization. STOC 2024: 1130-1140 - [c258]Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang:
A New Information Complexity Measure for Multi-pass Streaming with Applications. STOC 2024: 1781-1792 - [c257]Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong:
Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond. STOC 2024: 1911-1922 - [e2]David P. Woodruff:
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024. SIAM 2024, ISBN 978-1-61197-791-2 [contents] - [i230]Zhou Lu, Qiuyi Zhang, Xinyi Chen, Fred Zhang, David P. Woodruff, Elad Hazan:
Adaptive Regret for Bandits Made Possible: Two Queries Suffice. CoRR abs/2401.09278 (2024) - [i229]Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, Michael Wunder:
Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond. CoRR abs/2402.17327 (2024) - [i228]Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, Guanghao Ye:
Improving the Bit Complexity of Communication for Distributed Convex Optimization. CoRR abs/2403.19146 (2024) - [i227]Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang:
A New Information Complexity Measure for Multi-pass Streaming with Applications. CoRR abs/2403.20283 (2024) - [i226]Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong:
Optimal Communication for Classic Functions in the Coordinator Model and Beyond. CoRR abs/2403.20307 (2024) - [i225]David P. Woodruff, Taisuke Yasuda:
Reweighted Solutions for Weighted Low Rank Approximation. CoRR abs/2406.02431 (2024) - [i224]David P. Woodruff, Taisuke Yasuda:
Coresets for Multiple ℓp Regression. CoRR abs/2406.02432 (2024) - [i223]Hossein Esfandiari, Vahab Mirrokni, Praneeth Kacham, David P. Woodruff, Peilin Zhong:
High-Dimensional Geometric Streaming for Nearly Low Rank Data. CoRR abs/2406.02910 (2024) - [i222]William Swartworth, David P. Woodruff:
Fast Sampling Based Sketches for Tensors. CoRR abs/2406.06735 (2024) - [i221]Ying Feng, Aayush Jain, David P. Woodruff:
Fast White-Box Adversarial Streaming Without a Random Oracle. CoRR abs/2406.06808 (2024) - [i220]Rajesh Jayaram, David P. Woodruff, Samson Zhou:
Streaming Algorithms with Few State Changes. CoRR abs/2406.06821 (2024) - [i219]Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, Jason Zhang:
Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut. CoRR abs/2406.13231 (2024) - [i218]Aashiq Muhamed, Oscar Li, David P. Woodruff, Mona T. Diab, Virginia Smith:
Grass: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients. CoRR abs/2406.17660 (2024) - [i217]David P. Woodruff, Taisuke Yasuda:
Nearly Linear Sparsification of ℓp Subspace Approximation. CoRR abs/2407.03262 (2024) - [i216]Praneeth Kacham, David P. Woodruff:
Faster Algorithms for Schatten-p Low Rank Approximation. CoRR abs/2407.11959 (2024) - [i215]Yi Li, Honghao Lin, David P. Woodruff:
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms. CoRR abs/2408.08494 (2024) - [i214]Milind Prabhu, David P. Woodruff:
Learning Multiple Secrets in Mastermind. CoRR abs/2409.06453 (2024) - [i213]Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou:
A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches. CoRR abs/2409.16153 (2024) - [i212]Ravindran Kannan, Chiranjib Bhattacharyya, Praneeth Kacham, David P. Woodruff:
LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions. CoRR abs/2410.05462 (2024) - [i211]William Swartworth, David P. Woodruff:
Tight Sampling Bounds for Eigenvalue Approximation. CoRR abs/2411.03227 (2024) - [i210]Hamed Shirzad, Honghao Lin, Ameya Velingker, Balaji Venkatachalam, David P. Woodruff, Danica J. Sutherland:
A Theory for Compressibility of Graph Transformers for Transductive Learning. CoRR abs/2411.13028 (2024) - [i209]Hamed Shirzad, Honghao Lin, Balaji Venkatachalam, Ameya Velingker, David P. Woodruff, Danica J. Sutherland:
Even Sparser Graph Transformers. CoRR abs/2411.16278 (2024) - [i208]Matthew Ding, Alexandro Garces, Jason Li, Honghao Lin, Jelani Nelson, Vihan Shah, David P. Woodruff:
Space Complexity of Minimum Cut Problems in Single-Pass Streams. CoRR abs/2412.01143 (2024) - [i207]David P. Woodruff, Samson Zhou:
Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters. CoRR abs/2412.05807 (2024) - [i206]Zhao Song, Ali Vakilian, David P. Woodruff, Samson Zhou:
On Socially Fair Low-Rank Approximation and Column Subset Selection. CoRR abs/2412.06063 (2024) - [i205]Praneeth Kacham, David P. Woodruff:
Approximating the Top Eigenvector in Random Order Streams. CoRR abs/2412.11963 (2024) - 2023
- [j40]David P. Woodruff:
Technical Perspective: Tapping the Link between Algorithmic Model Counting and Streaming. Commun. ACM 66(9): 94 (2023) - [j39]Rajesh Jayaram, David P. Woodruff:
Towards Optimal Moment Estimation in Streaming and Distributed Models. ACM Trans. Algorithms 19(3): 27:1-27:35 (2023) - [j38]Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang:
Recovery From Non-Decomposable Distance Oracles. IEEE Trans. Inf. Theory 69(10): 6443-6469 (2023) - [j37]Elbert Du, Michael Mitzenmacher, David P. Woodruff, Guang Yang:
Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams. Theory Comput. 19: 1-44 (2023) - [c256]Tung Mai, Alexander Munteanu, Cameron Musco, Anup Rao, Chris Schwiegelshohn, David P. Woodruff:
Optimal Sketching Bounds for Sparse Linear Regression. AISTATS 2023: 11288-11316 - [c255]Yi Li, Honghao Lin, David P. Woodruff:
ℓp-Regression in the Arbitrary Partition Model of Communication. COLT 2023: 4902-4928 - [c254]Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou:
On Differential Privacy and Adaptive Data Analysis with Bounded Space. EUROCRYPT (3) 2023: 35-65 - [c253]Vincent Cohen-Addad, David P. Woodruff, Samson Zhou:
Streaming Euclidean k-median and k-means with o(log n) Space. FOCS 2023: 883-908 - [c252]Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff:
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming. FOCS 2023: 1515-1550 - [c251]Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David P. Woodruff:
Learning the Positions in CountSketch. ICLR 2023 - [c250]Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou:
Robust Algorithms on Adaptive Inputs from Bounded Adversaries. ICLR 2023 - [c249]Alexander Munteanu, Simon Omlor, David P. Woodruff:
Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression. ICLR 2023 - [c248]Ying Feng, David P. Woodruff:
Improved Algorithms for White-Box Adversarial Streams. ICML 2023: 9962-9975 - [c247]Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou:
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. ICML 2023: 34952-34977 - [c246]David P. Woodruff, Taisuke Yasuda:
Sharper Bounds for ℓp Sensitivity Sampling. ICML 2023: 37238-37272 - [c245]Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang:
Recovery from Non-Decomposable Distance Oracles. ITCS 2023: 73:1-73:22 - [c244]Gregory Dexter, Petros Drineas, David P. Woodruff, Taisuke Yasuda:
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming. NeurIPS 2023 - [c243]Praneeth Kacham, David P. Woodruff:
Lower Bounds on Adaptive Sensing for Matrix Recovery. NeurIPS 2023 - [c242]Swati Padmanabhan, David P. Woodruff, Richard Zhang:
Computing Approximate 𝓁p Sensitivities. NeurIPS 2023 - [c241]Tamás Sarlós, Xingyou Song, David P. Woodruff, Richard Zhang:
Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products. NeurIPS 2023 - [c240]David P. Woodruff, Peilin Zhong, Samson Zhou:
Near-Optimal k-Clustering in the Sliding Window Model. NeurIPS 2023 - [c239]David P. Woodruff, Fred Zhang, Samson Zhou:
On Robust Streaming for Learning with Experts: Algorithms and Lower Bounds. NeurIPS 2023 - [c238]Yi Li, Honghao Lin, David P. Woodruff:
The ℓp-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines. SODA 2023: 850-877 - [c237]Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou:
Near-Linear Sample Complexity for Lp Polynomial Regression. SODA 2023: 3959-4025 - [c236]Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. SODA 2023: 4026-4049 - [c235]David P. Woodruff, Taisuke Yasuda:
Online Lewis Weight Sampling. SODA 2023: 4622-4666 - [c234]William Swartworth, David P. Woodruff:
Optimal Eigenvalue Approximation via Sketching. STOC 2023: 145-155 - [c233]David P. Woodruff, Taisuke Yasuda:
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online. STOC 2023: 1802-1813 - [i204]Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou:
On Differential Privacy and Adaptive Data Analysis with Bounded Space. CoRR abs/2302.05707 (2023) - [i203]David P. Woodruff, Fred Zhang, Samson Zhou:
Streaming Algorithms for Learning with Experts: Deterministic Versus Robust. CoRR abs/2303.01709 (2023) - [i202]Alexander Munteanu, Simon Omlor, David P. Woodruff:
Almost Linear Constant-Factor Sketching for 𝓁1 and Logistic Regression. CoRR abs/2304.00051 (2023) - [i201]Tung Mai, Alexander Munteanu, Cameron Musco, Anup B. Rao, Chris Schwiegelshohn, David P. Woodruff:
Optimal Sketching Bounds for Sparse Linear Regression. CoRR abs/2304.02261 (2023) - [i200]Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff:
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming. CoRR abs/2304.06853 (2023) - [i199]Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou:
Robust Algorithms on Adaptive Inputs from Bounded Adversaries. CoRR abs/2304.07413 (2023) - [i198]David P. Woodruff, Taisuke Yasuda:
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online. CoRR abs/2304.09217 (2023) - [i197]William Swartworth, David P. Woodruff:
Optimal Eigenvalue Approximation via Sketching. CoRR abs/2304.09281 (2023) - [i196]Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff:
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. CoRR abs/2305.05826 (2023) - [i195]David P. Woodruff, Taisuke Yasuda:
Sharper Bounds for 𝓁p Sensitivity Sampling. CoRR abs/2306.00732 (2023) - [i194]Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou:
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. CoRR abs/2306.01869 (2023) - [i193]Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David P. Woodruff:
Learning the Positions in CountSketch. CoRR abs/2306.06611 (2023) - [i192]Ying Feng, David P. Woodruff:
Improved Algorithms for White-Box Adversarial Streams. CoRR abs/2307.03529 (2023) - [i191]Yi Li, Honghao Lin, David P. Woodruff:
𝓁p-Regression in the Arbitrary Partition Model of Communication. CoRR abs/2307.05117 (2023) - [i190]Hai Pham, Young Jin Kim, Subhabrata Mukherjee, David P. Woodruff, Barnabás Póczos, Hany Hassan Awadalla:
Task-Based MoE for Multitask Multilingual Machine Translation. CoRR abs/2308.15772 (2023) - [i189]Vincent Cohen-Addad, David P. Woodruff, Samson Zhou:
Streaming Euclidean k-median and k-means with o(log n) Space. CoRR abs/2310.02882 (2023) - [i188]Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, Amir Zandieh:
HyperAttention: Long-context Attention in Near-Linear Time. CoRR abs/2310.05869 (2023) - [i187]Gregory Dexter, Petros Drineas, David P. Woodruff, Taisuke Yasuda:
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming. CoRR abs/2310.19068 (2023) - [i186]David P. Woodruff, Peilin Zhong, Samson Zhou:
Near-Optimal k-Clustering in the Sliding Window Model. CoRR abs/2311.00642 (2023) - [i185]Tamás Sarlós, Xingyou Song, David P. Woodruff, Qiuyi Zhang:
Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products. CoRR abs/2311.01960 (2023) - [i184]Swati Padmanabhan, David P. Woodruff, Qiuyi (Richard) Zhang:
Computing Approximate 𝓁p Sensitivities. CoRR abs/2311.04158 (2023) - [i183]Praneeth Kacham, David P. Woodruff:
Lower Bounds on Adaptive Sensing for Matrix Recovery. CoRR abs/2311.17281 (2023) - [i182]Justin Y. Chen, Piotr Indyk, David P. Woodruff:
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions. CoRR abs/2311.17868 (2023) - [i181]Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou:
On Differential Privacy and Adaptive Data Analysis with Bounded Space. IACR Cryptol. ePrint Arch. 2023: 171 (2023) - 2022
- [j36]Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev:
A Framework for Adversarially Robust Streaming Algorithms. J. ACM 69(2): 17:1-17:33 (2022) - [j35]David P. Woodruff:
Technical Perspective: Model Counting Meets Distinct Elements in a Data Stream. SIGMOD Rec. 51(1): 86 (2022) - [j34]Ruosong Wang, David P. Woodruff:
Tight Bounds for ℓ1 Oblivious Subspace Embeddings. ACM Trans. Algorithms 18(1): 8:1-8:32 (2022) - [c232]Yi Li, Honghao Lin, David P. Woodruff, Yuheng Zhang:
Streaming Algorithms with Large Approximation Factors. APPROX/RANDOM 2022: 13:1-13:23 - [c231]Sepideh Mahabadi, David P. Woodruff, Samson Zhou:
Adaptive Sketches for Robust Regression with Importance Sampling. APPROX/RANDOM 2022: 31:1-31:21 - [c230]Deanna Needell, William Swartworth, David P. Woodruff:
Testing Positive Semidefiniteness Using Linear Measurements. FOCS 2022: 87-97 - [c229]David P. Woodruff, Taisuke Yasuda:
High-Dimensional Geometric Streaming in Polynomial Space. FOCS 2022: 732-743 - [c228]Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda:
Active Linear Regression for ℓp Norms and Beyond. FOCS 2022: 744-753 - [c227]Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang:
Triangle and Four Cycle Counting with Predictions in Graph Streams. ICLR 2022 - [c226]Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Learning-Augmented $k$-means Clustering. ICLR 2022 - [c225]Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou:
Fast Regression for Structured Inputs. ICLR 2022 - [c224]Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin, David P. Woodruff:
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra. ICML 2022: 3879-3900 - [c223]Praneeth Kacham, David P. Woodruff:
Sketching Algorithms and Lower Bounds for Ridge Regression. ICML 2022: 10539-10556 - [c222]Honghao Lin, Tian Luo, David P. Woodruff:
Learning Augmented Binary Search Trees. ICML 2022: 13431-13440 - [c221]Alexander Munteanu, Simon Omlor, Zhao Song, David P. Woodruff:
Bounding the Width of Neural Networks via Coupled Initialization A Worst Case Analysis. ICML 2022: 16083-16122 - [c220]David P. Woodruff, Amir Zandieh:
Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time. ICML 2022: 23933-23964 - [c219]Anubhav Baweja, Justin Jia, David P. Woodruff:
An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes. ITCS 2022: 16:1-16:23 - [c218]Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou:
Noisy Boolean Hidden Matching with Applications. ITCS 2022: 91:1-91:19 - [c217]David P. Woodruff, Fred Zhang, Richard Zhang:
Optimal Query Complexities for Dynamic Trace Estimation. NeurIPS 2022 - [c216]Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou:
The White-Box Adversarial Data Stream Model. PODS 2022: 15-27 - [c215]Rajesh Jayaram, David P. Woodruff, Samson Zhou:
Truly Perfect Samplers for Data Streams and Sliding Windows. PODS 2022: 29-40 - [c214]Agniva Chowdhury, Aritra Bose, Samson Zhou, David P. Woodruff, Petros Drineas:
A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World. RECOMB 2022: 86-106 - [c213]Piotr Indyk, Shyam Narayanan, David P. Woodruff:
Frequency Estimation with One-Sided Error. SODA 2022: 695-707 - [c212]David P. Woodruff, Taisuke Yasuda:
Improved Algorithms for Low Rank Approximation from Sparsity. SODA 2022: 2358-2403 - [c211]Nadiia Chepurko, Kenneth L. Clarkson, Praneeth Kacham, David P. Woodruff:
Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. SODA 2022: 3043-3068 - [c210]Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff:
Low-rank approximation with 1/ε1/3 matrix-vector products. STOC 2022: 1130-1143 - [c209]Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou:
Memory bounds for the experts problem. STOC 2022: 1158-1171 - [e1]Mikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff:
49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France. LIPIcs 229, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022, ISBN 978-3-95977-235-8 [contents] - [i180]David P. Woodruff, Amir Zandieh:
Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time. CoRR abs/2202.04515 (2022) - [i179]Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff:
Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products. CoRR abs/2202.05120 (2022) - [i178]Yi Li, David P. Woodruff:
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. CoRR abs/2202.09797 (2022) - [i177]Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou:
Fast Regression for Structured Inputs. CoRR abs/2203.07557 (2022) - [i176]Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang:
Triangle and Four Cycle Counting with Predictions in Graph Streams. CoRR abs/2203.09572 (2022) - [i175]Deanna Needell, William Swartworth, David P. Woodruff:
Testing Positive Semidefiniteness Using Linear Measurements. CoRR abs/2204.03782 (2022) - [i174]David P. Woodruff, Taisuke Yasuda:
High-Dimensional Geometric Streaming in Polynomial Space. CoRR abs/2204.03790 (2022) - [i173]Praneeth Kacham, David P. Woodruff:
Sketching Algorithms and Lower Bounds for Ridge Regression. CoRR abs/2204.06653 (2022) - [i172]Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou:
The White-Box Adversarial Data Stream Model. CoRR abs/2204.09136 (2022) - [i171]Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou:
Memory Bounds for the Experts Problem. CoRR abs/2204.09837 (2022) - [i170]Honghao Lin, Tian Luo, David P. Woodruff:
Learning Augmented Binary Search Trees. CoRR abs/2206.12110 (2022) - [i169]Alexander Munteanu, Simon Omlor, Zhao Song, David P. Woodruff:
Bounding the Width of Neural Networks via Coupled Initialization - A Worst Case Analysis. CoRR abs/2206.12802 (2022) - [i168]Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang:
Low Rank Approximation for General Tensor Networks. CoRR abs/2207.07417 (2022) - [i167]Sepideh Mahabadi, David P. Woodruff, Samson Zhou:
Adaptive Sketches for Robust Regression with Importance Sampling. CoRR abs/2207.07822 (2022) - [i166]Yi Li, Honghao Lin, David P. Woodruff, Yuheng Zhang:
Streaming Algorithms with Large Approximation Factors. CoRR abs/2207.08075 (2022) - [i165]David P. Woodruff, Taisuke Yasuda:
Online Lewis Weight Sampling. CoRR abs/2207.08268 (2022) - [i164]Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang:
Recovery from Non-Decomposable Distance Oracles. CoRR abs/2209.05676 (2022) - [i163]David P. Woodruff, Fred Zhang, Qiuyi Zhang:
Optimal Query Complexities for Dynamic Trace Estimation. CoRR abs/2209.15219 (2022) - [i162]Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou:
Near-Linear Sample Complexity for Lp Polynomial Regression. CoRR abs/2211.06790 (2022) - [i161]Yi Li, Honghao Lin, David P. Woodruff:
The 𝓁p-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines. CoRR abs/2211.07132 (2022) - [i160]Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. CoRR abs/2211.09964 (2022) - 2021
- [j33]David P. Woodruff, Mikolaj Bojanczyk:
ICALP 2022 - 49th EATCS International Colloquium on Automata, Languages and Programming. Bull. EATCS 135 (2021) - [j32]Rajesh Jayaram, David P. Woodruff:
Perfect Lp Sampling in a Data Stream. SIAM J. Comput. 50(2): 382-439 (2021) - [j31]Yi Li, Ruosong Wang, David P. Woodruff:
Tight Bounds for the Subspace Sketch Problem with Applications. SIAM J. Comput. 50(4): 1287-1335 (2021) - [j30]Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev:
A Framework for Adversarially Robust Streaming Algorithms. SIGMOD Rec. 50(1): 6-13 (2021) - [j29]Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang:
Querying a Matrix through Matrix-Vector Products. ACM Trans. Algorithms 17(4): 31:1-31:19 (2021) - [j28]Fan Yang, Sifan Liu, Edgar Dobriban, David P. Woodruff:
How to Reduce Dimension With PCA and Random Projections? IEEE Trans. Inf. Theory 67(12): 8154-8189 (2021) - [c208]Yi Li, David P. Woodruff:
The Product of Gaussian Matrices Is Close to Gaussian. APPROX-RANDOM 2021: 35:1-35:22 - [c207]Akshay Kamath, Eric Price, David P. Woodruff:
A Simple Proof of a New Set Disjointness with Applications to Data Streams. CCC 2021: 37:1-37:24 - [c206]Praneeth Kacham, David P. Woodruff:
Reduced-Rank Regression with Operator Norm Error. COLT 2021: 2679-2716 - [c205]Yi Li, David P. Woodruff, Taisuke Yasuda:
Exponentially Improved Dimensionality Reduction for l1: Subspace Embeddings and Independence Testing. COLT 2021: 3111-3195 - [c204]Cyrus Rashtchian, David P. Woodruff, Peng Ye, Hanlin Zhu:
Average-Case Communication Complexity of Statistical Problems. COLT 2021: 3859-3886 - [c203]David P. Woodruff, Samson Zhou:
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. FOCS 2021: 1183-1196 - [c202]David P. Woodruff:
A Very Sketchy Talk (Invited Talk). ICALP 2021: 6:1-6:8 - [c201]David P. Woodruff, Samson Zhou:
Separations for Estimating Large Frequency Moments on Data Streams. ICALP 2021: 112:1-112:21 - [c200]Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou:
Learning a Latent Simplex in Input Sparsity Time. ICLR 2021 - [c199]Zhili Feng, Praneeth Kacham, David P. Woodruff:
Dimensionality Reduction for the Sum-of-Distances Metric. ICML 2021: 3220-3229 - [c198]Rajesh Jayaram, Alireza Samadian, David P. Woodruff, Peng Ye:
In-Database Regression in Input Sparsity Time. ICML 2021: 4797-4806 - [c197]Shuli Jiang, Dennis Li, Irene Mengze Li, Arvind V. Mahankali, David P. Woodruff:
Streaming and Distributed Algorithms for Robust Column Subset Selection. ICML 2021: 4971-4981 - [c196]Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David P. Woodruff:
Single Pass Entrywise-Transformed Low Rank Approximation. ICML 2021: 4982-4991 - [c195]Alexander Munteanu, Simon Omlor, David P. Woodruff:
Oblivious Sketching for Logistic Regression. ICML 2021: 7861-7871 - [c194]Zhao Song, David P. Woodruff, Zheng Yu, Lichen Zhang:
Fast Sketching of Polynomial Kernels of Polynomial Degree. ICML 2021: 9812-9823 - [c193]Cameron Musco, Christopher Musco, David P. Woodruff:
Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation. ITCS 2021: 6:1-6:20 - [c192]Piotr Indyk, Tal Wagner, David P. Woodruff:
Few-Shot Data-Driven Algorithms for Low Rank Approximation. NeurIPS 2021: 10678-10690 - [c191]Arvind V. Mahankali, David P. Woodruff:
Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters. NeurIPS 2021: 14407-14420 - [c190]Shuli Jiang, Hai Pham, David P. Woodruff, Qiuyi (Richard) Zhang:
Optimal Sketching for Trace Estimation. NeurIPS 2021: 23741-23753 - [c189]Graham Cormode, Charlie Dickens, David P. Woodruff:
Subspace Exploration: Bounds on Projected Frequency Estimation. PODS 2021: 273-284 - [c188]Arvind V. Mahankali, David P. Woodruff:
Optimal ℓ1 Column Subset Selection and a Fast PTAS for Low Rank Approximation. SODA 2021: 560-578 - [c187]Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff:
Hutch++: Optimal Stochastic Trace Estimation. SOSA 2021: 142-155 - [c186]Zhili Feng, Fred Roosta, David P. Woodruff:
Non-PSD matrix sketching with applications to regression and optimization. UAI 2021: 1841-1851 - [i159]Graham Cormode, Charlie Dickens, David P. Woodruff:
Subspace exploration: Bounds on Projected Frequency Estimation. CoRR abs/2101.07546 (2021) - [i158]Yi Li, Honghao Lin, David P. Woodruff:
Learning-Augmented Sketches for Hessians. CoRR abs/2102.12317 (2021) - [i157]Yi Li, David P. Woodruff, Taisuke Yasuda:
Exponentially Improved Dimensionality Reduction for 𝓁1: Subspace Embeddings and Independence Testing. CoRR abs/2104.12946 (2021) - [i156]David P. Woodruff, Samson Zhou:
Separations for Estimating Large Frequency Moments on Data Streams. CoRR abs/2105.03773 (2021) - [i155]Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou:
Learning a Latent Simplex in Input-Sparsity Time. CoRR abs/2105.08005 (2021) - [i154]Akshay Kamath, Eric Price, David P. Woodruff:
A Simple Proof of a New Set Disjointness with Applications to Data Streams. CoRR abs/2105.11338 (2021) - [i153]Zhili Feng, Fred Roosta, David P. Woodruff:
Non-PSD Matrix Sketching with Applications to Regression and Optimization. CoRR abs/2106.08544 (2021) - [i152]Cyrus Rashtchian, David P. Woodruff, Peng Ye, Hanlin Zhu:
Average-Case Communication Complexity of Statistical Problems. CoRR abs/2107.01335 (2021) - [i151]Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou:
Noisy Boolean Hidden Matching with Applications. CoRR abs/2107.02578 (2021) - [i150]Shuchi Chawla, Jelani Nelson, Chris Umans, David P. Woodruff:
Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020. CoRR abs/2107.02846 (2021) - [i149]Rajesh Jayaram, Alireza Samadian, David P. Woodruff, Peng Ye:
In-Database Regression in Input Sparsity Time. CoRR abs/2107.05672 (2021) - [i148]Alexander Munteanu, Simon Omlor, David P. Woodruff:
Oblivious sketching for logistic regression. CoRR abs/2107.06615 (2021) - [i147]Anubhav Baweja, Justin Jia, David P. Woodruff:
An Efficient Semi-Streaming PTAS for Tournament Feedback ArcSet with Few Passes. CoRR abs/2107.07141 (2021) - [i146]Shuli Jiang, Dongyu Li, Irene Mengze Li, Arvind V. Mahankali, David P. Woodruff:
Streaming and Distributed Algorithms for Robust Column Subset Selection. CoRR abs/2107.07657 (2021) - [i145]Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David P. Woodruff:
Single Pass Entrywise-Transformed Low Rank Approximation. CoRR abs/2107.07889 (2021) - [i144]Nadiia Chepurko, Kenneth L. Clarkson, Praneeth Kacham, David P. Woodruff:
Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. CoRR abs/2107.08090 (2021) - [i143]Zhao Song, David P. Woodruff, Zheng Yu, Lichen Zhang:
Fast Sketching of Polynomial Kernels of Polynomial Degree. CoRR abs/2108.09420 (2021) - [i142]Yi Li, David P. Woodruff:
The Product of Gaussian Matrices is Close to Gaussian. CoRR abs/2108.09887 (2021) - [i141]Rajesh Jayaram, David P. Woodruff, Samson Zhou:
Truly Perfect Samplers for Data Streams and Sliding Windows. CoRR abs/2108.12017 (2021) - [i140]Jon Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Learning-Augmented k-means Clustering. CoRR abs/2110.14094 (2021) - [i139]Shuli Jiang, Hai Pham, David P. Woodruff, Qiuyi (Richard) Zhang:
Optimal Sketching for Trace Estimation. CoRR abs/2111.00664 (2021) - [i138]David P. Woodruff, Taisuke Yasuda:
Improved Algorithms for Low Rank Approximation from Sparsity. CoRR abs/2111.00668 (2021) - [i137]Piotr Indyk, Shyam Narayanan, David P. Woodruff:
Frequency Estimation with One-Sided Error. CoRR abs/2111.03953 (2021) - [i136]Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda:
Active Sampling for Linear Regression Beyond the $\ell_2$ Norm. CoRR abs/2111.04888 (2021) - 2020
- [j27]Yin Tat Lee, Marcin Pilipczuk, David P. Woodruff:
Introduction to the Special Issue on SODA'18. ACM Trans. Algorithms 16(1): 1:1-1:2 (2020) - [c185]Praneeth Kacham, David P. Woodruff:
Optimal Deterministic Coresets for Ridge Regression. AISTATS 2020: 4141-4150 - [c184]Hang Liao, Barak A. Pearlmutter, Vamsi K. Potluru, David P. Woodruff:
Automatic Differentiation of Sketched Regression. AISTATS 2020: 4367-4376 - [c183]Cyrus Rashtchian, David P. Woodruff, Hanlin Zhu:
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems. APPROX-RANDOM 2020: 26:1-26:20 - [c182]Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff:
Streaming Complexity of SVMs. APPROX-RANDOM 2020: 50:1-50:22 - [c181]Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff:
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. APPROX-RANDOM 2020: 64:1-64:22 - [c180]Mark Braverman, Sumegha Garg, David P. Woodruff:
The Coin Problem with Applications to Data Streams. FOCS 2020: 318-329 - [c179]Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff:
Robust and Sample Optimal Algorithms for PSD Low Rank Approximation. FOCS 2020: 506-516 - [c178]Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou:
Near Optimal Linear Algebra in the Online and Sliding Window Models. FOCS 2020: 517-528 - [c177]Rajesh Jayaram, David P. Woodruff, Qiuyi Zhang:
Span Recovery for Deep Neural Networks with Applications to Input Obfuscation. ICLR 2020 - [c176]Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, David P. Woodruff:
Learning-Augmented Data Stream Algorithms. ICLR 2020 - [c175]Yi Li, David P. Woodruff:
Input-Sparsity Low Rank Approximation in Schatten Norm. ICML 2020: 6001-6009 - [c174]David P. Woodruff, Amir Zandieh:
Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling. ICML 2020: 10324-10333 - [c173]Manuel Fernandez, David P. Woodruff, Taisuke Yasuda:
Graph Spanners in the Message-Passing Model. ITCS 2020: 77:1-77:18 - [c172]Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff:
Pseudo-Deterministic Streaming. ITCS 2020: 79:1-79:25 - [c171]Edith Cohen, Rasmus Pagh, David P. Woodruff:
WOR and p's: Sketches for ℓp-Sampling Without Replacement. NeurIPS 2020 - [c170]Quang Minh Hoang, Nghia Hoang, Hai Pham, David P. Woodruff:
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes. NeurIPS 2020 - [c169]Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev:
A Framework for Adversarially Robust Streaming Algorithms. PODS 2020: 63-80 - [c168]Debmalya Mandal, Nisarg Shah, David P. Woodruff:
Optimal Communication-Distortion Tradeoff in Voting. EC 2020: 795-813 - [c167]Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh:
Oblivious Sketching of High-Degree Polynomial Kernels. SODA 2020: 141-160 - [c166]Yi Li, Ruosong Wang, David P. Woodruff:
Tight Bounds for the Subspace Sketch Problem with Applications. SODA 2020: 1655-1674 - [c165]Santosh S. Vempala, Ruosong Wang, David P. Woodruff:
The Communication Complexity of Optimization. SODA 2020: 1733-1752 - [c164]Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou:
Non-adaptive adaptive sampling on turnstile streams. STOC 2020: 1251-1264 - [c163]Cyrus Rashtchian, Aneesh Sharma, David P. Woodruff:
LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew. WWW 2020: 2998-3004 - [i135]Rajesh Jayaram, David P. Woodruff, Qiuyi Zhang:
Span Recovery for Deep Neural Networks with Applications to Input Obfuscation. CoRR abs/2002.08202 (2020) - [i134]Cyrus Rashtchian, Aneesh Sharma, David P. Woodruff:
LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew. CoRR abs/2003.02972 (2020) - [i133]Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev:
A Framework for Adversarially Robust Streaming Algorithms. CoRR abs/2003.14265 (2020) - [i132]Zhao Song, David P. Woodruff, Peilin Zhong:
Average Case Column Subset Selection for Entrywise 𝓁1-Norm Loss. CoRR abs/2004.07986 (2020) - [i131]Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou:
Non-Adaptive Adaptive Sampling on Turnstile Streams. CoRR abs/2004.10969 (2020) - [i130]Yi Li, David P. Woodruff:
Input-Sparsity Low Rank Approximation in Schatten Norm. CoRR abs/2004.12646 (2020) - [i129]Agniva Chowdhury, Petros Drineas, David P. Woodruff, Samson Zhou:
Approximation Algorithms for Sparse Principal Component Analysis. CoRR abs/2006.12748 (2020) - [i128]Cyrus Rashtchian, David P. Woodruff, Hanlin Zhu:
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems. CoRR abs/2006.14015 (2020) - [i127]Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff:
Streaming Complexity of SVMs. CoRR abs/2007.03633 (2020) - [i126]David P. Woodruff, Amir Zandieh:
Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling. CoRR abs/2007.03927 (2020) - [i125]Edith Cohen, Rasmus Pagh, David P. Woodruff:
WOR and p's: Sketches for 𝓁p-Sampling Without Replacement. CoRR abs/2007.06744 (2020) - [i124]Simin Liu, Tianrui Liu, Ali Vakilian, Yulin Wan, David P. Woodruff:
On Learned Sketches for Randomized Numerical Linear Algebra. CoRR abs/2007.09890 (2020) - [i123]Arvind V. Mahankali, David P. Woodruff:
Optimal 𝓁1 Column Subset Selection and a Fast PTAS for Low Rank Approximation. CoRR abs/2007.10307 (2020) - [i122]Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff:
Hutch++: Optimal Stochastic Trace Estimation. CoRR abs/2010.09649 (2020) - [i121]Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, David P. Woodruff:
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra. CoRR abs/2011.04125 (2020) - [i120]Praneeth Kacham, David P. Woodruff:
Reduced-Rank Regression with Operator Norm Error. CoRR abs/2011.04564 (2020) - [i119]David P. Woodruff, Samson Zhou:
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. CoRR abs/2011.07471 (2020) - [i118]Quang Minh Hoang, Trong Nghia Hoang, Hai Pham, David P. Woodruff:
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes. CoRR abs/2011.08432 (2020) - [i117]Mark Braverman, Sumegha Garg, David P. Woodruff:
The Coin Problem with Applications to Data Streams. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j26]Maria-Florina Balcan, Yingyu Liang, Zhao Song, David P. Woodruff, Hongyang Zhang:
Non-Convex Matrix Completion and Related Problems via Strong Duality. J. Mach. Learn. Res. 20: 102:1-102:56 (2019) - [j25]Yi Li, Huy L. Nguyen, David P. Woodruff:
On Approximating Matrix Norms in Data Streams. SIAM J. Comput. 48(6): 1643-1697 (2019) - [j24]Arnab Bhattacharyya, Palash Dey, David P. Woodruff:
An Optimal Algorithm for ℓ1-Heavy Hitters in Insertion Streams and Related Problems. ACM Trans. Algorithms 15(1): 2:1-2:27 (2019) - [c162]Xiaofei Shi, David P. Woodruff:
Sublinear Time Numerical Linear Algebra for Structured Matrices. AAAI 2019: 4918-4925 - [c161]John Hainline, Brendan Juba, Hai S. Le, David P. Woodruff:
Conditional Sparse $L_p$-norm Regression With Optimal Probability. AISTATS 2019: 1042-1050 - [c160]Manuel Fernandez, David P. Woodruff, Taisuke Yasuda:
The Query Complexity of Mastermind with lp Distances. APPROX-RANDOM 2019: 1:1-1:11 - [c159]Rajesh Jayaram, David P. Woodruff:
Towards Optimal Moment Estimation in Streaming and Distributed Models. APPROX-RANDOM 2019: 29:1-29:21 - [c158]Ainesh Bakshi, Rajesh Jayaram, David P. Woodruff:
Learning Two Layer Rectified Neural Networks in Polynomial Time. COLT 2019: 195-268 - [c157]Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff:
Faster Algorithms for High-Dimensional Robust Covariance Estimation. COLT 2019: 727-757 - [c156]Piotr Indyk, Ali Vakilian, Tal Wagner, David P. Woodruff:
Sample-Optimal Low-Rank Approximation of Distance Matrices. COLT 2019: 1723-1751 - [c155]Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang:
The One-Way Communication Complexity of Dynamic Time Warping Distance. SoCG 2019: 16:1-16:15 - [c154]Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff:
On Coresets for Logistic Regression. GI-Jahrestagung 2019: 267-268 - [c153]Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, David P. Woodruff:
Robust Communication-Optimal Distributed Clustering Algorithms. ICALP 2019: 18:1-18:16 - [c152]Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang:
Querying a Matrix Through Matrix-Vector Products. ICALP 2019: 94:1-94:16 - [c151]David P. Woodruff, Guang Yang:
Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams. ICALP 2019: 97:1-97:14 - [c150]Kenneth L. Clarkson, Ruosong Wang, David P. Woodruff:
Dimensionality Reduction for Tukey Regression. ICML 2019: 1262-1271 - [c149]Ravi Kumar, Rina Panigrahy, Ali Rahimi, David P. Woodruff:
Faster Algorithms for Binary Matrix Factorization. ICML 2019: 3551-3559 - [c148]Taisuke Yasuda, David P. Woodruff, Manuel Fernandez:
Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-means Clustering. ICML 2019: 7055-7063 - [c147]Huaian Diao, Zhao Song, David P. Woodruff, Xin Yang:
Total Least Squares Regression in Input Sparsity Time. NeurIPS 2019: 2478-2489 - [c146]Frank Ban, David P. Woodruff, Qiuyi (Richard) Zhang:
Regularized Weighted Low Rank Approximation. NeurIPS 2019: 4061-4071 - [c145]Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, David P. Woodruff:
Optimal Sketching for Kronecker Product Regression and Low Rank Approximation. NeurIPS 2019: 4739-4750 - [c144]Zhao Song, David P. Woodruff, Peilin Zhong:
Towards a Zero-One Law for Column Subset Selection. NeurIPS 2019: 6120-6131 - [c143]Debmalya Mandal, Ariel D. Procaccia, Nisarg Shah, David P. Woodruff:
Efficient and Thrifty Voting by Any Means Necessary. NeurIPS 2019: 7178-7189 - [c142]Michela Meister, Tamás Sarlós, David P. Woodruff:
Tight Dimensionality Reduction for Sketching Low Degree Polynomial Kernels. NeurIPS 2019: 9470-9481 - [c141]Zhao Song, David P. Woodruff, Peilin Zhong:
Average Case Column Subset Selection for Entrywise 퓁1-Norm Loss. NeurIPS 2019: 10111-10121 - [c140]Rajesh Jayaram, Gokarna Sharma, Srikanta Tirthapura, David P. Woodruff:
Weighted Reservoir Sampling from Distributed Streams. PODS 2019: 218-235 - [c139]Can Kockan, Kaiyuan Zhu, Natnatee Dokmai, Nikolai Karpov, M. Oguzhan Külekci, David P. Woodruff, Süleyman Cenk Sahinalp:
Sketching Algorithms for Genomic Data Analysis and Querying in a Secure Enclave. RECOMB 2019: 302-304 - [c138]Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang:
Testing Matrix Rank, Optimally. SODA 2019: 727-746 - [c137]Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff:
A PTAS for ℓp-Low Rank Approximation. SODA 2019: 747-766 - [c136]Ruosong Wang, David P. Woodruff:
Tight Bounds for ℓp Oblivious Subspace Embeddings. SODA 2019: 1825-1843 - [c135]Zhao Song, David P. Woodruff, Peilin Zhong:
Relative Error Tensor Low Rank Approximation. SODA 2019: 2772-2789 - [i116]Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff:
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. CoRR abs/1902.10328 (2019) - [i115]Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang:
The One-Way Communication Complexity of Dynamic Time Warping Distance. CoRR abs/1903.03520 (2019) - [i114]Srikanta Tirthapura, David P. Woodruff:
Optimal Random Sampling from Distributed Streams Revisited. CoRR abs/1903.12065 (2019) - [i113]Rajesh Jayaram, Gokarna Sharma, Srikanta Tirthapura, David P. Woodruff:
Weighted Reservoir Sampling from Distributed Streams. CoRR abs/1904.04126 (2019) - [i112]Yi Li, Ruosong Wang, David P. Woodruff:
Tight Bounds for the Subspace Sketch Problem with Applications. CoRR abs/1904.05543 (2019) - [i111]Cameron Musco, Christopher Musco, David P. Woodruff:
Low-Rank Approximation from Communication Complexity. CoRR abs/1904.09841 (2019) - [i110]Kenneth L. Clarkson, Ruosong Wang, David P. Woodruff:
Dimensionality Reduction for Tukey Regression. CoRR abs/1905.05376 (2019) - [i109]Manuel Fernandez, David P. Woodruff, Taisuke Yasuda:
Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel k-means Clustering. CoRR abs/1905.06394 (2019) - [i108]David P. Woodruff, Guang Yang:
Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams. CoRR abs/1905.07135 (2019) - [i107]Piotr Indyk, Ali Vakilian, Tal Wagner, David P. Woodruff:
Sample-Optimal Low-Rank Approximation of Distance Matrices. CoRR abs/1906.00339 (2019) - [i106]Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff:
Faster Algorithms for High-Dimensional Robust Covariance Estimation. CoRR abs/1906.04661 (2019) - [i105]Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang:
Querying a Matrix through Matrix-Vector Products. CoRR abs/1906.05736 (2019) - [i104]Santosh S. Vempala, Ruosong Wang, David P. Woodruff:
The Communication Complexity of Optimization. CoRR abs/1906.05832 (2019) - [i103]Rajesh Jayaram, David P. Woodruff:
Towards Optimal Moment Estimation in Streaming and Distributed Models. CoRR abs/1907.05816 (2019) - [i102]Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh:
Oblivious Sketching of High-Degree Polynomial Kernels. CoRR abs/1909.01410 (2019) - [i101]Manuel Fernandez, David P. Woodruff, Taisuke Yasuda:
The Query Complexity of Mastermind with 𝓁p Distances. CoRR abs/1909.10668 (2019) - [i100]Huaian Diao, Zhao Song, David P. Woodruff, Xin Yang:
Total Least Squares Regression in Input Sparsity Time. CoRR abs/1909.12441 (2019) - [i99]Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, David P. Woodruff:
Optimal Sketching for Kronecker Product Regression and Low Rank Approximation. CoRR abs/1909.13384 (2019) - [i98]Manuel Fernandez, David P. Woodruff, Taisuke Yasuda:
Graph Spanners in the Message-Passing Model. CoRR abs/1911.05991 (2019) - [i97]Frank Ban, David P. Woodruff, Qiuyi (Richard) Zhang:
Regularized Weighted Low Rank Approximation. CoRR abs/1911.06958 (2019) - [i96]Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff:
Pseudo-deterministic Streaming. CoRR abs/1911.11368 (2019) - [i95]Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff:
Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation. CoRR abs/1912.04177 (2019) - [i94]Xiaofei Shi, David P. Woodruff:
Sublinear Time Numerical Linear Algebra for Structured Matrices. CoRR abs/1912.06060 (2019) - [i93]Zhili Feng, Praneeth Kacham, David P. Woodruff:
Strong Coresets for Subspace Approximation and k-Median in Nearly Linear Time. CoRR abs/1912.12003 (2019) - [i92]Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff:
Pseudo-deterministic Streaming. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [c134]Huaian Diao, Zhao Song, Wen Sun, David P. Woodruff:
Sketching for Kronecker Product Regression and P-splines. AISTATS 2018: 1299-1308 - [c133]Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou:
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. APPROX-RANDOM 2018: 7:1-7:22 - [c132]Aditya Krishnan, Sidhanth Mohanty, David P. Woodruff:
On Sketching the q to p Norms. APPROX-RANDOM 2018: 15:1-15:20 - [c131]Yi Li, Vasileios Nakos, David P. Woodruff:
On Low-Risk Heavy Hitters and Sparse Recovery Schemes. APPROX-RANDOM 2018: 19:1-19:13 - [c130]Rajesh Jayaram, David P. Woodruff:
Perfect Lp Sampling in a Data Stream. FOCS 2018: 544-555 - [c129]Christian Sohler, David P. Woodruff:
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension. FOCS 2018: 802-813 - [c128]Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang:
Revisiting Frequency Moment Estimation in Random Order Streams. ICALP 2018: 25:1-25:14 - [c127]Sumit Ganguly, David P. Woodruff:
High Probability Frequency Moment Sketches. ICALP 2018: 58:1-58:15 - [c126]Vasileios Nakos, Xiaofei Shi, David P. Woodruff, Hongyang Zhang:
Improved Algorithms for Adaptive Compressed Sensing. ICALP 2018: 90:1-90:14 - [c125]Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, Lin F. Yang:
Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order. ICML 2018: 648-657 - [c124]Graham Cormode, Charlie Dickens, David P. Woodruff:
Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski p-Norms. ICML 2018: 1048-1056 - [c123]Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, Hongyang Zhang:
Matrix Completion and Related Problems via Strong Duality. ITCS 2018: 5:1-5:22 - [c122]Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff:
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. ITCS 2018: 8:1-8:21 - [c121]Yogesh Dahiya, Dimitris Konomis, David P. Woodruff:
An Empirical Evaluation of Sketching for Numerical Linear Algebra. KDD 2018: 1292-1300 - [c120]Ainesh Bakshi, David P. Woodruff:
Sublinear Time Low-Rank Approximation of Distance Matrices. NeurIPS 2018: 3786-3796 - [c119]Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff:
On Coresets for Logistic Regression. NeurIPS 2018: 6562-6571 - [c118]Roie Levin, Anish Prasad Sevekari, David P. Woodruff:
Robust Subspace Approximation in a Stream. NeurIPS 2018: 10706-10716 - [c117]Rajesh Jayaram, David P. Woodruff:
Data Streams with Bounded Deletions. PODS 2018: 341-354 - [c116]David P. Woodruff, Qin Zhang:
Distributed Statistical Estimation of Matrix Products with Applications. PODS 2018: 383-394 - [r2]David P. Woodruff:
Frequency Moments. Encyclopedia of Database Systems (2nd ed.) 2018 - [i91]Ruosong Wang, David P. Woodruff:
Tight Bounds for 𝓁p Oblivious Subspace Embeddings. CoRR abs/1801.04414 (2018) - [i90]Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang:
Revisiting Frequency Moment Estimation in Random Order Streams. CoRR abs/1803.02270 (2018) - [i89]Rajesh Jayaram, David P. Woodruff:
Data Streams with Bounded Deletions. CoRR abs/1803.08777 (2018) - [i88]Vasileios Nakos, Xiaofei Shi, David P. Woodruff, Hongyang Zhang:
Improved Algorithms for Adaptive Compressed Sensing. CoRR abs/1804.09673 (2018) - [i87]Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou:
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. CoRR abs/1805.00212 (2018) - [i86]Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou:
Near Optimal Linear Algebra in the Online and Sliding Window Models. CoRR abs/1805.03765 (2018) - [i85]Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff:
On Coresets for Logistic Regression. CoRR abs/1805.08571 (2018) - [i84]Sumit Ganguly, David P. Woodruff:
High Probability Frequency Moment Sketches. CoRR abs/1805.10885 (2018) - [i83]Aditya Krishnan, Sidhanth Mohanty, David P. Woodruff:
On Sketching the q to p norms. CoRR abs/1806.06429 (2018) - [i82]John Hainline, Brendan Juba, Hai S. Le, David P. Woodruff:
Conditional Sparse 𝓁p-norm Regression With Optimal Probability. CoRR abs/1806.10222 (2018) - [i81]David P. Woodruff, Qin Zhang:
Distributed Statistical Estimation of Matrix Products with Applications. CoRR abs/1807.00878 (2018) - [i80]Graham Cormode, Charlie Dickens, David P. Woodruff:
Leveraging Well-Conditioned Bases: Streaming \& Distributed Summaries in Minkowski p-Norms. CoRR abs/1807.02571 (2018) - [i79]Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff:
A PTAS for 𝓁p-Low Rank Approximation. CoRR abs/1807.06101 (2018) - [i78]Rajesh Jayaram, David P. Woodruff:
Perfect Lp Sampling in a Data Stream. CoRR abs/1808.05497 (2018) - [i77]Christian Sohler, David P. Woodruff:
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension. CoRR abs/1809.02961 (2018) - [i76]Ainesh Bakshi, David P. Woodruff:
Sublinear Time Low-Rank Approximation of Distance Matrices. CoRR abs/1809.06986 (2018) - [i75]Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang:
Testing Matrix Rank, Optimally. CoRR abs/1810.08171 (2018) - [i74]Zhao Song, David P. Woodruff, Peilin Zhong:
Towards a Zero-One Law for Entrywise Low Rank Approximation. CoRR abs/1811.01442 (2018) - [i73]Ainesh Bakshi, Rajesh Jayaram, David P. Woodruff:
Learning Two Layer Rectified Neural Networks in Polynomial Time. CoRR abs/1811.01885 (2018) - [i72]Zhao Song, David P. Woodruff, Peilin Zhong:
Relative Error Tensor Low Rank Approximation. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j23]David P. Woodruff, Qin Zhang:
When distributed computation is communication expensive. Distributed Comput. 30(5): 309-323 (2017) - [j22]Christos Boutsidis, David P. Woodruff:
Optimal CUR Matrix Decompositions. SIAM J. Comput. 46(2): 543-589 (2017) - [j21]Haim Avron, Kenneth L. Clarkson, David P. Woodruff:
Faster Kernel Ridge Regression Using Sketching and Preconditioning. SIAM J. Matrix Anal. Appl. 38(4): 1116-1138 (2017) - [c115]Haim Avron, Kenneth L. Clarkson, David P. Woodruff:
Sharper Bounds for Regularized Data Fitting. APPROX-RANDOM 2017: 27:1-27:22 - [c114]David P. Woodruff:
Sketching for Geometric Problems (Invited Talk). ESA 2017: 1:1-1:5 - [c113]Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh:
Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams. FOCS 2017: 475-486 - [c112]Cameron Musco, David P. Woodruff:
Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices. FOCS 2017: 672-683 - [c111]Eric Price, Zhao Song, David P. Woodruff:
Fast Regression with an $ell_infty$ Guarantee. ICALP 2017: 59:1-59:14 - [c110]Yi Li, David P. Woodruff:
Embeddings of Schatten Norms with Applications to Data Streams. ICALP 2017: 60:1-60:14 - [c109]Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, David P. Woodruff:
Algorithms for $\ell_p$ Low-Rank Approximation. ICML 2017: 806-814 - [c108]Xingguo Li, Jarvis D. Haupt, David P. Woodruff:
Near Optimal Sketching of Low-Rank Tensor Regression. NIPS 2017: 3466-3476 - [c107]Cameron Musco, David P. Woodruff:
Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? NIPS 2017: 4435-4445 - [c106]Karl Bringmann, Pavel Kolev, David P. Woodruff:
Approximation Algorithms for l0-Low Rank Approximation. NIPS 2017: 6648-6659 - [c105]Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff:
BPTree: An ℓ2 Heavy Hitters Algorithm Using Constant Memory. PODS 2017: 361-376 - [c104]Santosh S. Vempala, David P. Woodruff:
Adaptive Matrix Vector Product. SODA 2017: 2044-2060 - [c103]Kenneth L. Clarkson, David P. Woodruff:
Low-Rank PSD Approximation in Input-Sparsity Time. SODA 2017: 2061-2072 - [c102]Zhao Song, David P. Woodruff, Peilin Zhong:
Low rank approximation with entrywise l1-norm error. STOC 2017: 688-701 - [i71]Jiecao Chen, He Sun, David P. Woodruff, Qin Zhang:
Communication-Optimal Distributed Clustering. CoRR abs/1702.00196 (2017) - [i70]Yi Li, David P. Woodruff:
Embeddings of Schatten Norms with Applications to Data Streams. CoRR abs/1702.05626 (2017) - [i69]Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh:
Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams. CoRR abs/1704.00633 (2017) - [i68]Cameron Musco, David P. Woodruff:
Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices. CoRR abs/1704.03371 (2017) - [i67]Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff:
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. CoRR abs/1704.04163 (2017) - [i66]Zhao Song, David P. Woodruff, Peilin Zhong:
Relative Error Tensor Low Rank Approximation. CoRR abs/1704.08246 (2017) - [i65]Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, Hongyang Zhang:
Optimal Sample Complexity for Matrix Completion and Related Problems via 𝓁s2-Regularization. CoRR abs/1704.08683 (2017) - [i64]Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, David P. Woodruff:
Algorithms for $\ell_p$ Low Rank Approximation. CoRR abs/1705.06730 (2017) - [i63]Eric Price, Zhao Song, David P. Woodruff:
Fast Regression with an $\ell_\infty$ Guarantee. CoRR abs/1705.10723 (2017) - [i62]Yi Li, Vasileios Nakos, David P. Woodruff:
On Low-Risk Heavy Hitters and Sparse Recovery Schemes. CoRR abs/1709.02919 (2017) - [i61]Jarvis D. Haupt, Xingguo Li, David P. Woodruff:
Near Optimal Sketching of Low-Rank Tensor Regression. CoRR abs/1709.07093 (2017) - [i60]Karl Bringmann, Pavel Kolev, David P. Woodruff:
Approximation Algorithms for ࡁ0-Low Rank Approximation. CoRR abs/1710.11253 (2017) - [i59]Cameron Musco, David P. Woodruff:
Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? CoRR abs/1711.01596 (2017) - [i58]Huaian Diao, Zhao Song, Wen Sun, David P. Woodruff:
Sketching for Kronecker Product Regression and P-splines. CoRR abs/1712.09473 (2017) - [i57]Martin Dietzfelbinger, Michael Mitzenmacher, Rasmus Pagh, David P. Woodruff, Martin Aumüller:
Theory and Applications of Hashing (Dagstuhl Seminar 17181). Dagstuhl Reports 7(5): 1-21 (2017) - [i56]Vladimir Braverman, David P. Woodruff, Ke Yi:
Processing Big Data Streams (NII Shonan Meeting 2017-7). NII Shonan Meet. Rep. 2017 (2017) - 2016
- [j20]Andrew McGregor, A. Pavan, Srikanta Tirthapura, David P. Woodruff:
Space-Efficient Estimation of Statistics Over Sub-Sampled Streams. Algorithmica 74(2): 787-811 (2016) - [j19]Mark Braverman, David P. Woodruff:
Guest Editorial for Information Complexity and Applications. Algorithmica 76(3): 595-596 (2016) - [j18]Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev:
Certifying Equality With Limited Interaction. Algorithmica 76(3): 796-845 (2016) - [j17]Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff:
The Fast Cauchy Transform and Faster Robust Linear Regression. SIAM J. Comput. 45(3): 763-810 (2016) - [j16]Mina Ghashami, Edo Liberty, Jeff M. Phillips, David P. Woodruff:
Frequent Directions: Simple and Deterministic Matrix Sketching. SIAM J. Comput. 45(5): 1762-1792 (2016) - [j15]Yuval Rabani, Andréa W. Richa, Jared Saia, David P. Woodruff:
Editorial to the Special Issue on SODA'12. ACM Trans. Algorithms 12(1): 1:1 (2016) - [j14]Yung-Yu Chung, Srikanta Tirthapura, David P. Woodruff:
A Simple Message-Optimal Algorithm for Random Sampling from a Distributed Stream. IEEE Trans. Knowl. Data Eng. 28(6): 1356-1368 (2016) - [c101]Yi Li, David P. Woodruff:
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. APPROX-RANDOM 2016: 39:1-39:11 - [c100]Yuqing Ai, Wei Hu, Yi Li, David P. Woodruff:
New Characterizations in Turnstile Streams with Applications. CCC 2016: 20:1-20:22 - [c99]Michael S. Crouch, Andrew McGregor, Gregory Valiant, David P. Woodruff:
Stochastic Streams: Sample Complexity vs. Space Complexity. ESA 2016: 32:1-32:15 - [c98]Michael B. Cohen, Jelani Nelson, David P. Woodruff:
Optimal Approximate Matrix Product in Terms of Stable Rank. ICALP 2016: 11:1-11:14 - [c97]David P. Woodruff, Peilin Zhong:
Distributed low rank approximation of implicit functions of a matrix. ICDE 2016: 847-858 - [c96]David P. Woodruff:
New Algorithms for Heavy Hitters in Data Streams (Invited Talk). ICDT 2016: 4:1-4:12 - [c95]Michael Kapralov, Vamsi K. Potluru, David P. Woodruff:
How to Fake Multiply by a Gaussian Matrix. ICML 2016: 2101-2110 - [c94]Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang:
On Sketching Quadratic Forms. ITCS 2016: 311-319 - [c93]Maria-Florina Balcan, Yingyu Liang, Le Song, David P. Woodruff, Bo Xie:
Communication Efficient Distributed Kernel Principal Component Analysis. KDD 2016: 725-734 - [c92]Zhao Song, David P. Woodruff, Huan Zhang:
Sublinear Time Orthogonal Tensor Decomposition. NIPS 2016: 793-801 - [c91]Jiecao Chen, He Sun, David P. Woodruff, Qin Zhang:
Communication-Optimal Distributed Clustering. NIPS 2016: 3720-3728 - [c90]Vladimir Braverman, Stephen R. Chestnut, David P. Woodruff, Lin F. Yang:
Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors. PODS 2016: 261-276 - [c89]Arnab Bhattacharyya, Palash Dey, David P. Woodruff:
An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems. PODS 2016: 385-400 - [c88]Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, David P. Woodruff:
Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching. SODA 2016: 318-337 - [c87]Hossein Esfandiari, MohammadTaghi Hajiaghayi, David P. Woodruff:
Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond. SPAA 2016: 397-399 - [c86]Christos Boutsidis, David P. Woodruff, Peilin Zhong:
Optimal principal component analysis in distributed and streaming models. STOC 2016: 236-249 - [c85]Ilya P. Razenshteyn, Zhao Song, David P. Woodruff:
Weighted low rank approximations with provable guarantees. STOC 2016: 250-263 - [c84]Yi Li, David P. Woodruff:
On approximating functions of the singular values in a stream. STOC 2016: 726-739 - [c83]Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff:
Beating CountSketch for heavy hitters in insertion streams. STOC 2016: 740-753 - [c82]Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff:
Communication lower bounds for statistical estimation problems via a distributed data processing inequality. STOC 2016: 1011-1020 - [i55]Vladimir Braverman, Stephen R. Chestnut, David P. Woodruff, Lin F. Yang:
Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors. CoRR abs/1601.07473 (2016) - [i54]David P. Woodruff, Peilin Zhong:
Distributed Low Rank Approximation of Implicit Functions of a Matrix. CoRR abs/1601.07721 (2016) - [i53]Arnab Bhattacharyya, Palash Dey, David P. Woodruff:
An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems. CoRR abs/1603.00213 (2016) - [i52]Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff:
BPTree: an ℓ2 heavy hitters algorithm using constant memory. CoRR abs/1603.00759 (2016) - [i51]David P. Woodruff:
New Algorithms for Heavy Hitters in Data Streams. CoRR abs/1603.01733 (2016) - [i50]Yi Li, David P. Woodruff:
On Approximating Functions of the Singular Values in a Stream. CoRR abs/1604.08679 (2016) - [i49]Michael Kapralov, Vamsi K. Potluru, David P. Woodruff:
How to Fake Multiply by a Gaussian Matrix. CoRR abs/1606.05732 (2016) - [i48]Zhao Song, David P. Woodruff, Peilin Zhong:
Low Rank Approximation with Entrywise ℓ1-Norm Error. CoRR abs/1611.00898 (2016) - [i47]Haim Avron, Kenneth L. Clarkson, David P. Woodruff:
Faster Kernel Ridge Regression Using Sketching and Preconditioning. CoRR abs/1611.03220 (2016) - [i46]Haim Avron, Kenneth L. Clarkson, David P. Woodruff:
Sharper Bounds for Regression and Low-Rank Approximation with Regularization. CoRR abs/1611.03225 (2016) - [i45]Ravindran Kannan, Michael W. Mahoney, David P. Woodruff:
Recent Advances in Randomized Numerical Linear Algebra (NII Shonan Meeting 2016-10). NII Shonan Meet. Rep. 2016 (2016) - 2015
- [j13]Srikanta Tirthapura, David P. Woodruff:
A General Method for Estimating Correlated Aggregates Over a Data Stream. Algorithmica 73(2): 235-260 (2015) - [c81]Xiaoming Sun, David P. Woodruff:
Tight Bounds for Graph Problems in Insertion Streams. APPROX-RANDOM 2015: 435-448 - [c80]Kenneth L. Clarkson, David P. Woodruff:
Input Sparsity and Hardness for Robust Subspace Approximation. FOCS 2015: 310-329 - [c79]Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev:
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity. ICALP (1) 2015: 960-972 - [c78]Omri Weinstein, David P. Woodruff:
The Simultaneous Communication of Disjointness with Applications to Data Streams. ICALP (1) 2015: 1082-1093 - [c77]Dirk Van Gucht, Ryan Williams, David P. Woodruff, Qin Zhang:
The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication. PODS 2015: 199-212 - [c76]Kenneth L. Clarkson, David P. Woodruff:
Sketching for M-Estimators: A Unified Approach to Robust Regression. SODA 2015: 921-939 - [i44]Mina Ghashami, Edo Liberty, Jeff M. Phillips, David P. Woodruff:
Frequent Directions : Simple and Deterministic Matrix Sketching. CoRR abs/1501.01711 (2015) - [i43]Maria-Florina Balcan, Yingyu Liang, Le Song, David P. Woodruff, Bo Xie:
Distributed Kernel Principal Component Analysis. CoRR abs/1503.06858 (2015) - [i42]Arturs Backurs, Piotr Indyk, Eric Price, Ilya P. Razenshteyn, David P. Woodruff:
Nearly-optimal bounds for sparse recovery in generic norms, with applications to $k$-median sketching. CoRR abs/1504.01076 (2015) - [i41]Christos Boutsidis, David P. Woodruff:
Communication-optimal Distributed Principal Component Analysis in the Column-partition Model. CoRR abs/1504.06729 (2015) - [i40]Hossein Esfandiari, MohammadTaghi Hajiaghayi, David P. Woodruff:
Applications of Uniform Sampling: Densest Subgraph and Beyond. CoRR abs/1506.04505 (2015) - [i39]Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff:
Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality. CoRR abs/1506.07216 (2015) - [i38]Michael B. Cohen, Jelani Nelson, David P. Woodruff:
Optimal approximate matrix product in terms of stable rank. CoRR abs/1507.02268 (2015) - [i37]Kenneth L. Clarkson, David P. Woodruff:
Input Sparsity and Hardness for Robust Subspace Approximation. CoRR abs/1510.06073 (2015) - [i36]Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff:
Beating CountSketch for Heavy Hitters in Insertion Streams. CoRR abs/1511.00661 (2015) - [i35]Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang:
On Sketching Quadratic Forms. CoRR abs/1511.06099 (2015) - [i34]Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev:
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity. Electron. Colloquium Comput. Complex. TR15 (2015) - [i33]Omri Weinstein, David P. Woodruff:
The Simultaneous Communication of Disjointness with Applications to Data Streams. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j12]Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev:
Steiner transitive-closure spanners of low-dimensional posets. Comb. 34(3): 255-277 (2014) - [j11]David P. Woodruff:
Data Streams and Applications in Computer Science. Bull. EATCS 114 (2014) - [j10]David P. Woodruff:
Sketching as a Tool for Numerical Linear Algebra. Found. Trends Theor. Comput. Sci. 10(1-2): 1-157 (2014) - [c75]Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev:
Certifying Equality With Limited Interaction. APPROX-RANDOM 2014: 545-581 - [c74]Ravi Kannan, Santosh S. Vempala, David P. Woodruff:
Principal Component Analysis and Higher Correlations for Distributed Data. COLT 2014: 1040-1057 - [c73]Yi Li, Zhengyu Wang, David P. Woodruff:
Improved testing of low rank matrices. KDD 2014: 691-700 - [c72]David P. Woodruff:
Low Rank Approximation Lower Bounds in Row-Update Streams. NIPS 2014: 1781-1789 - [c71]Haim Avron, Huy L. Nguyen, David P. Woodruff:
Subspace Embeddings for the Polynomial Kernel. NIPS 2014: 2258-2266 - [c70]Yingyu Liang, Maria-Florina Balcan, Vandana Kanchanapally, David P. Woodruff:
Improved Distributed Principal Component Analysis. NIPS 2014: 3113-3121 - [c69]Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev:
Beyond set disjointness: the communication complexity of finding the intersection. PODC 2014: 106-113 - [c68]Michael Kapralov, David P. Woodruff:
Spanners and sparsifiers in dynamic streams. PODC 2014: 272-281 - [c67]Rasmus Pagh, Morten Stöckel, David P. Woodruff:
Is min-wise hashing optimal for summarizing set intersection? PODS 2014: 109-120 - [c66]David P. Woodruff, Qin Zhang:
An Optimal Lower Bound for Distinct Elements in the Message Passing Model. SODA 2014: 718-733 - [c65]Yi Li, Huy L. Nguyen, David P. Woodruff:
On Sketching Matrix Norms and the Top Singular Vector. SODA 2014: 1562-1581 - [c64]Yi Li, Huy L. Nguyen, David P. Woodruff:
Turnstile streaming algorithms might as well be linear sketches. STOC 2014: 174-183 - [c63]Christos Boutsidis, David P. Woodruff:
Optimal CUR matrix decompositions. STOC 2014: 353-362 - [c62]Yi Li, Xiaoming Sun, Chengu Wang, David P. Woodruff:
On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model. DISC 2014: 499-513 - [i32]Alexandr Andoni, Robert Krauthgamer, David P. Woodruff:
The Sketching Complexity of Graph Cuts. CoRR abs/1403.7058 (2014) - [i31]Christos Boutsidis, David P. Woodruff:
Optimal CUR Matrix Decompositions. CoRR abs/1405.7910 (2014) - [i30]Yi Li, Xiaoming Sun, Chengu Wang, David P. Woodruff:
On The Communication Complexity of Linear Algebraic Problems in the Message Passing Model. CoRR abs/1407.4755 (2014) - [i29]Maria-Florina Balcan, Vandana Kanchanapally, Yingyu Liang, David P. Woodruff:
Improved Distributed Principal Component Analysis. CoRR abs/1408.5823 (2014) - [i28]David P. Woodruff:
Sketching as a Tool for Numerical Linear Algebra. CoRR abs/1411.4357 (2014) - [i27]Jiecao Chen, Bo Qin, David P. Woodruff, Qin Zhang:
A Sketching Algorithm for Spectral Graph Sparsification. CoRR abs/1412.8225 (2014) - 2013
- [j9]Benny Kimelfeld, Jan Vondrák, David P. Woodruff:
Multi-Tuple Deletion Propagation: Approximations and Complexity. Proc. VLDB Endow. 6(13): 1558-1569 (2013) - [j8]T. S. Jayram, David P. Woodruff:
Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error. ACM Trans. Algorithms 9(3): 26:1-26:17 (2013) - [c61]Yi Li, David P. Woodruff:
A Tight Lower Bound for High Frequency Moment Estimation with Small Error. APPROX-RANDOM 2013: 623-638 - [c60]David P. Woodruff, Qin Zhang:
Subspace Embeddings and \(\ell_p\)-Regression Using Exponential Random Variables. COLT 2013: 546-567 - [c59]Haim Avron, Vikas Sindhwani, David P. Woodruff:
Sketching Structured Matrices for Faster Nonlinear Regression. NIPS 2013: 2994-3002 - [c58]Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff:
The Fast Cauchy Transform and Faster Robust Linear Regression. SODA 2013: 466-477 - [c57]Eric Price, David P. Woodruff:
Lower Bounds for Adaptive Sparse Recovery. SODA 2013: 652-663 - [c56]Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev:
Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching. SODA 2013: 1738-1756 - [c55]Kenneth L. Clarkson, David P. Woodruff:
Low rank approximation and regression in input sparsity time. STOC 2013: 81-90 - [c54]Moritz Hardt, David P. Woodruff:
How robust are linear sketches to adaptive inputs? STOC 2013: 121-130 - [c53]David P. Woodruff, Qin Zhang:
When Distributed Computation Is Communication Expensive. DISC 2013: 16-30 - [i26]David P. Woodruff, Qin Zhang:
When Distributed Computation does not Help. CoRR abs/1304.4636 (2013) - [i25]David P. Woodruff, Qin Zhang:
Subspace Embeddings and ℓp-Regression Using Exponential Random Variables. CoRR abs/1305.5580 (2013) - 2012
- [j7]Kenneth L. Clarkson, Elad Hazan, David P. Woodruff:
Sublinear optimization for machine learning. J. ACM 59(5): 23:1-23:49 (2012) - [j6]David P. Woodruff:
A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. J. Comput. Sci. Technol. 27(4): 678-686 (2012) - [j5]Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff:
Fast approximation of matrix coherence and statistical leverage. J. Mach. Learn. Res. 13: 3475-3506 (2012) - [j4]Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-Closure Spanners. SIAM J. Comput. 41(6): 1380-1425 (2012) - [j3]Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. SIAM J. Discret. Math. 26(2): 618-646 (2012) - [c52]Jelani Nelson, Huy L. Nguyên, David P. Woodruff:
On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation. APPROX-RANDOM 2012: 627-638 - [c51]Srikanta Tirthapura, David P. Woodruff:
A General Method for Estimating Correlated Aggregates over a Data Stream. ICDE 2012: 162-173 - [c50]Michael W. Mahoney, Petros Drineas, Malik Magdon-Ismail, David P. Woodruff:
Fast approximation of matrix coherence and statistical leverage. ICML 2012 - [c49]Eric Price, David P. Woodruff:
Applications of the Shannon-Hartley theorem to data streams and sparse recovery. ISIT 2012: 2446-2450 - [c48]Andrew McGregor, A. Pavan, Srikanta Tirthapura, David P. Woodruff:
Space-efficient estimation of statistics over sub-sampled streams. PODS 2012: 273-282 - [c47]Srikanta Tirthapura, David P. Woodruff:
Rectangle-efficient aggregation in spatial data streams. PODS 2012: 283-294 - [c46]Anna C. Gilbert, Brett Hemenway, Martin J. Strauss, David P. Woodruff, Mary Wootters:
Reusable low-error compressive sampling schemes through privacy. SSP 2012: 536-539 - [c45]David P. Woodruff, Qin Zhang:
Tight bounds for distributed functional monitoring. STOC 2012: 941-960 - [i24]Eric Price, David P. Woodruff:
Lower Bounds for Adaptive Sparse Recovery. CoRR abs/1205.3518 (2012) - [i23]Jelani Nelson, Huy L. Nguyên, David P. Woodruff:
On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation. CoRR abs/1206.5725 (2012) - [i22]Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff:
The Fast Cauchy Transform: with Applications to Basis Construction, Regression, and Subspace Approximation in L1. CoRR abs/1207.4684 (2012) - [i21]Kenneth L. Clarkson, David P. Woodruff:
Low Rank Approximation and Regression in Input Sparsity Time. CoRR abs/1207.6365 (2012) - [i20]Moritz Hardt, David P. Woodruff:
How Robust are Linear Sketches to Adaptive Inputs? CoRR abs/1211.1056 (2012) - 2011
- [c44]Joshua Brody, David P. Woodruff:
Streaming Algorithms with One-Sided Estimation. APPROX-RANDOM 2011: 436-447 - [c43]Rolf Klein, Rainer Penninger, Christian Sohler, David P. Woodruff:
Tolerant Algorithms. ESA 2011: 736-747 - [c42]Piotr Indyk, Eric Price, David P. Woodruff:
On the Power of Adaptivity in Sparse Recovery. FOCS 2011: 285-294 - [c41]Eric Price, David P. Woodruff:
(1 + eps)-Approximate Sparse Recovery. FOCS 2011: 295-304 - [c40]Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev:
Steiner Transitive-Closure Spanners of Low-Dimensional Posets. ICALP (1) 2011: 760-772 - [c39]Arnab Bhattacharyya, Piotr Indyk, David P. Woodruff, Ning Xie:
The Complexity of Linear Dependence Problems in Vector Spaces. ICS 2011: 496-508 - [c38]T. S. Jayram, David P. Woodruff:
Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error. SODA 2011: 1-10 - [c37]David P. Woodruff:
Near-optimal private approximation protocols via a black box transformation. STOC 2011: 735-744 - [c36]Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff:
Fast moment estimation in data streams in optimal space. STOC 2011: 745-754 - [c35]Christian Sohler, David P. Woodruff:
Subspace embeddings for the L1-norm with applications. STOC 2011: 755-764 - [c34]Srikanta Tirthapura, David P. Woodruff:
Optimal Random Sampling from Distributed Streams Revisited. DISC 2011: 283-297 - [i19]Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff:
Lower Bounds for Sparse Recovery. CoRR abs/1106.0365 (2011) - [i18]Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff:
Fast approximation of matrix coherence and statistical leverage. CoRR abs/1109.3843 (2011) - [i17]Piotr Indyk, Eric Price, David P. Woodruff:
On the Power of Adaptivity in Sparse Recovery. CoRR abs/1110.3850 (2011) - [i16]Eric Price, David P. Woodruff:
(1+eps)-approximate Sparse Recovery. CoRR abs/1110.4414 (2011) - [i15]David P. Woodruff, Qin Zhang:
Tight Bounds for Distributed Functional Monitoring. CoRR abs/1112.5153 (2011) - 2010
- [j2]Alexandre V. Evfimievski, Ronald Fagin, David P. Woodruff:
Epistemic privacy. J. ACM 58(1): 2:1-2:45 (2010) - [c33]Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. APPROX-RANDOM 2010: 448-461 - [c32]David P. Woodruff:
A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. APPROX-RANDOM 2010: 766-779 - [c31]Kenneth L. Clarkson, Elad Hazan, David P. Woodruff:
Sublinear Optimization for Machine Learning. FOCS 2010: 449-457 - [c30]David P. Woodruff:
Additive Spanners in Nearly Quadratic Time. ICALP (1) 2010: 463-474 - [c29]Daniel M. Kane, Jelani Nelson, David P. Woodruff:
An optimal algorithm for the distinct elements problem. PODS 2010: 41-52 - [c28]Jelani Nelson, David P. Woodruff:
Fast Manhattan sketches in data streams. PODS 2010: 99-110 - [c27]Dan Feldman, Morteza Monemizadeh, Christian Sohler, David P. Woodruff:
Coresets and Sketches for High Dimensional Subspace Approximation Problems. SODA 2010: 630-649 - [c26]Morteza Monemizadeh, David P. Woodruff:
1-Pass Relative-Error Lp-Sampling with Applications. SODA 2010: 1143-1160 - [c25]Daniel M. Kane, Jelani Nelson, David P. Woodruff:
On the Exact Space Complexity of Sketching and Streaming Small Norms. SODA 2010: 1161-1178 - [c24]Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff:
Lower Bounds for Sparse Recovery. SODA 2010: 1190-1197 - [i14]Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff:
Fast Moment Estimation in Data Streams in Optimal Space. CoRR abs/1007.4191 (2010) - [i13]Kenneth L. Clarkson, Elad Hazan, David P. Woodruff:
Sublinear Optimization for Machine Learning. CoRR abs/1010.4408 (2010) - [i12]Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev:
Steiner Transitive-Closure Spanners of d-Dimensional Posets. CoRR abs/1011.6100 (2010)
2000 – 2009
- 2009
- [c23]Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff:
Efficient Sketches for Earth-Mover Distance, with Applications. FOCS 2009: 324-330 - [c22]T. S. Jayram, David P. Woodruff:
The Data Stream Space Complexity of Cascaded Norms. FOCS 2009: 765-774 - [c21]David P. Woodruff:
The average-case complexity of counting distinct elements. ICDT 2009: 284-295 - [c20]Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-closure spanners. SODA 2009: 932-941 - [c19]Kenneth L. Clarkson, David P. Woodruff:
Numerical linear algebra in the streaming model. STOC 2009: 205-214 - [r1]David P. Woodruff:
Frequency Moments. Encyclopedia of Database Systems 2009: 1169-1170 - [i11]Jelani Nelson, David P. Woodruff:
A Near-Optimal Algorithm for L1-Difference. CoRR abs/0904.2027 (2009) - [i10]Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-Closure Spanners of the Hypercube and the Hypergrid. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [c18]David P. Woodruff:
Corruption and Recovery-Efficient Locally Decodable Codes. APPROX-RANDOM 2008: 584-595 - [c17]Alexandre V. Evfimievski, Ronald Fagin, David P. Woodruff:
Epistemic privacy. PODS 2008: 171-180 - [i9]Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-Closure Spanners. CoRR abs/0808.1787 (2008) - [i8]Daniel M. Kane, Jelani Nelson, David P. Woodruff:
Revisiting Norm Estimation in Data Streams. CoRR abs/0811.3648 (2008) - 2007
- [b1]David P. Woodruff:
Efficient and private distance approximation in the communication and streaming models. Massachusetts Institute of Technology, Cambridge, MA, USA, 2007 - [j1]David P. Woodruff, Sergey Yekhanin:
A Geometric Approach to Information-Theoretic Private Information Retrieval. SIAM J. Comput. 37(4): 1046-1056 (2007) - [c16]David P. Woodruff:
Revisiting the Efficiency of Malicious Two-Party Computation. EUROCRYPT 2007: 79-96 - [c15]Xiaoming Sun, David P. Woodruff:
The communication and streaming complexity of computing the longest common and increasing subsequences. SODA 2007: 336-345 - [i7]David P. Woodruff:
New Lower Bounds for General Locally Decodable Codes. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [c14]David P. Woodruff:
Better Approximations for the Minimum Common Integer Partition Problem. APPROX-RANDOM 2006: 248-259 - [c13]Zulfikar Ramzan, David P. Woodruff:
Fast Algorithms for the Free Riders Problem in Broadcast Encryption. CRYPTO 2006: 308-325 - [c12]Craig Gentry, Zulfikar Ramzan, David P. Woodruff:
Explicit Exclusive Set Systems with Applications to Broadcast Encryption. FOCS 2006: 27-38 - [c11]David P. Woodruff:
Lower Bounds for Additive Spanners, Emulators, and More. FOCS 2006: 389-398 - [c10]Piotr Indyk, David P. Woodruff:
Polylogarithmic Private Approximations and Efficient Matching. TCC 2006: 245-264 - [i6]Zulfikar Ramzan, David P. Woodruff:
Fast Algorithms for the Free Riders Problem in Broadcast Encryption. IACR Cryptol. ePrint Arch. 2006: 293 (2006) - [i5]David P. Woodruff:
Revisiting the Efficiency of Malicious Two-Party Computation. IACR Cryptol. ePrint Arch. 2006: 397 (2006) - 2005
- [c9]David P. Woodruff, Sergey Yekhanin:
A Geometric Approach to Information-Theoretic Private Information Retrieval. CCC 2005: 275-284 - [c8]Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, David P. Woodruff:
Practical Cryptography in High Dimensional Tori. EUROCRYPT 2005: 234-250 - [c7]Piotr Indyk, David P. Woodruff:
Optimal approximations of the frequency moments of data streams. STOC 2005: 202-208 - [i4]David P. Woodruff, Sergey Yekhanin:
A Geometric Approach to Information-Theoretic Private Information Retrieval. Electron. Colloquium Comput. Complex. TR05 (2005) - [i3]Piotr Indyk, David P. Woodruff:
Polylogarithmic Private Approximations and Efficient Matching. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [c6]David P. Woodruff, Jessica Staddon:
Private inference control. CCS 2004: 188-197 - [c5]Marten van Dijk, David P. Woodruff:
Asymptotically Optimal Communication for Torus-Based Cryptography. CRYPTO 2004: 157-178 - [c4]Hanson Zhou, David P. Woodruff:
Clustering via Matrix Powering. PODS 2004: 136-142 - [c3]David P. Woodruff:
Optimal space lower bounds for all frequency moments. SODA 2004: 167-175 - [i2]David P. Woodruff, Jessica Staddon:
Private Inference Control. IACR Cryptol. ePrint Arch. 2004: 130 (2004) - [i1]Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, David P. Woodruff:
Practical Cryptography in High Dimensional Tori. IACR Cryptol. ePrint Arch. 2004: 352 (2004) - 2003
- [c2]Piotr Indyk, David P. Woodruff:
Tight Lower Bounds for the Distinct Elements Problem. FOCS 2003: 283-288 - 2002
- [c1]David P. Woodruff, Marten van Dijk:
Cryptography in an Unbounded Computational Model. EUROCRYPT 2002: 149-164
Coauthor Index
Vahab S. Mirrokni
aka: Vahab Mirrokni
aka: Vahab Mirrokni
William Swartworth
aka: William J. Swartworth
aka: William J. Swartworth
[j43] [c283] [i240] [i239] [i237] [i231] [j42] [c280] [c266] [c261] [i220] [i213] [i207] [i206] [c254] [c253] [c250] [c247] [c240] [c239] [c237] [c236] [i204] [i203] [i199] [i194] [i189] [i186] [i181] [c231] [c226] [c225] [c218] [c216] [c215] [c214] [c209] [i177] [i172] [i171] [i167] [i162] [i160] [c203] [c201] [c200] [i156] [i155] [i151] [i141] [i140] [c178] [c164] [i131] [i129] [i119] [c133] [i87] [i86]
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
[+][–] Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
[+][–] Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-07-19 03:12 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
