Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDDavid P. Woodruff
Person information
- affiliation: Carnegie Mellon University, PA, USA
- affiliation (former): IBM Almaden Research Center
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
[j39]David P. Woodruff:
Technical Perspective: Tapping the Link between Algorithmic Model Counting and Streaming. Commun. ACM 66(9): 94 (2023)- [j38]Rajesh Jayaram
, David P. Woodruff:
Towards Optimal Moment Estimation in Streaming and Distributed Models. ACM Trans. Algorithms 19(3): 27:1-27:35 (2023) - [j37]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) - [c248]Tung Mai, Alexander Munteanu, Cameron Musco, Anup Rao, Chris Schwiegelshohn, David P. Woodruff:
Optimal Sketching Bounds for Sparse Linear Regression. AISTATS 2023: 11288-11316 - [c247]Yi Li, Honghao Lin, David P. Woodruff:
ℓp-Regression in the Arbitrary Partition Model of Communication. COLT 2023: 4902-4928 - [c246]Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou:
On Differential Privacy and Adaptive Data Analysis with Bounded Space. EUROCRYPT (3) 2023: 35-65 - [c245]Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David P. Woodruff:
Learning the Positions in CountSketch. ICLR 2023 - [c244]Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou:
Robust Algorithms on Adaptive Inputs from Bounded Adversaries. ICLR 2023 - [c243]Alexander Munteanu, Simon Omlor, David P. Woodruff:
Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression. ICLR 2023 - [c242]Ying Feng, David P. Woodruff:
Improved Algorithms for White-Box Adversarial Streams. ICML 2023: 9962-9975 - [c241]Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou:
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. ICML 2023: 34952-34977 - [c240]David P. Woodruff, Taisuke Yasuda:
Sharper Bounds for ℓp Sensitivity Sampling. ICML 2023: 37238-37272 - [c239]Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang:
Recovery from Non-Decomposable Distance Oracles. ITCS 2023: 73:1-73:22 - [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]