Skip to content
cs-conference-ranking.org

David P. Woodruff

Publication record assembled from the DBLP archive of ranked conferences.

Papers indexed

219

Venues

26

Active years

2002–2026

Best venue rank

A*

Where they publish

Papers

219 indexed papers, newest first.

YearVenueTitleAuthors
2026ICALPStreaming Complexity Separations for Dense and Sparse Graphs.Yang P. Liu, Hoai-An Nguyen, Noah G. Singer, David P. Woodruff
2026ISITProgress on the Courtade-Kumar Conjecture: Optimal High-Noise Entropy Bounds and Generalized Coordinate-wise Mutual Information.Adel Javanmard, David P. Woodruff
2026SODAOnline Learning with Limited Information in the Sliding Window Model.Vladimir Braverman, Sumegha Garg, Chen Wang, David P. Woodruff, Samson Zhou
2026SODALHonghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, Samson Zhou
2026STOCCombinatorial Optimization using Comparison Oracles.Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider, David P. Woodruff
2026STOCAdversarial Robustness on Insertion-Deletion Streams.Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou
2025FOCSPerfect Lp Sampling with Polylogarithmic Update Time.William Swartworth, David P. Woodruff, Samson Zhou
2025FOCSRoot Ridge Leverage Score Sampling for ℓp Subspace Approximation.David P. Woodruff, Taisuke Yasuda
2025ICALPGuessing Efficiently for Constrained Subspace Approximation.Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu, Ali Vakilian, David P. Woodruff
2025ICALPTight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model.Shiyuan Feng, William Swartworth, David P. Woodruff
2025ICLRStreaming Algorithms For ℓp Flows and ℓp Regression.Amit Chakrabarti, Jeffrey Jiang, David P. Woodruff, Taisuke Yasuda
2025ICLRLevAttention: Time, Space and Streaming Efficient Algorithm for Heavy Attentions.Ravindran Kannan, Chiranjib Bhattacharyya, Praneeth Kacham, David P. Woodruff
2025ICLRBeyond Worst-Case Dimensionality Reduction for Sparse Vectors.Sandeep Silwal, David P. Woodruff, Qiuyi Zhang
2025ICMLOn Fine-Grained Distinct Element Estimation.Ilias Diakonikolas, Daniel Kane, Jasper C. H. Lee, Thanasis Pittas, David P. Woodruff, Samson Zhou
2025ICMLMaximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures.Alina Ene, Alessandro Epasto, Vahab Mirrokni, Hoai-An Nguyen, Huy L. Nguyen, David P. Woodruff, Peilin Zhong
2025ICMLOn Differential Privacy for Adaptively Solving Search Problems via Sketching.Shiyuan Feng, Ying Feng, George Zhaoqi Li, Zhao Song, David P. Woodruff, Lichen Zhang
2025ICMLRobust Sparsification via Sensitivity.Chansophea Wathanak In, Yi Li, David P. Woodruff, Xuan Wu
2025ICMLUnderstanding the Kronecker Matrix-Vector Complexity of Linear Algebra.Raphael A. Meyer, William J. Swartworth, David P. Woodruff
2025SODATight Sampling Bounds for Eigenvalue Approximation.William Swartworth, David P. Woodruff
2025STOCLifting Linear Sketches: Optimal Bounds and Adversarial Robustness.Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou
2024EMNLPGRASS: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients.Aashiq Muhamed, Oscar Li, David P. Woodruff, Mona T. Diab, Virginia Smith
2024FOCSA Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches.Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou
2024ICLROptimal Sketching for Residual Error Estimation for Matrix and Vector Norms.Yi Li, Honghao Lin, David P. Woodruff
2024ICLRHyperAttention: Long-context Attention in Near-Linear Time.Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, Amir Zandieh
2024ICLRAdaptive Regret for Bandits Made Possible: Two Queries Suffice.Zhou Lu, Qiuyi Zhang, Xinyi Chen, Fred Zhang, David P. Woodruff, Elad Hazan
2024ICMLData-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond.Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, Michael Wunder
2024ICMLHigh-Dimensional Geometric Streaming for Nearly Low Rank Data.Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong
2024ICMLFast White-Box Adversarial Streaming Without a Random Oracle.Ying Feng, Aayush Jain, David P. Woodruff
2024ICMLLearning Multiple Secrets in Mastermind.Milind Prabhu, David P. Woodruff
2024ICMLFast Sampling-Based Sketches for Tensors.William J. Swartworth, David P. Woodruff
2024ICMLReweighted Solutions for Weighted Low Rank Approximation.David P. Woodruff, Taisuke Yasuda
2024ICMLCoresets for Multiple ℓp Regression.David P. Woodruff, Taisuke Yasuda
2024PODSApproximation Algorithms on Matrices - With Some Database Applications!David P. Woodruff
2024STOCA New Information Complexity Measure for Multi-pass Streaming with Applications.Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang
2024STOCOptimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond.Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong
2024STOCImproving the Bit Complexity of Communication for Distributed Convex Optimization.Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, Guanghao Ye
2023AISTATSOptimal Sketching Bounds for Sparse Linear Regression.Tung Mai, Alexander Munteanu, Cameron Musco, Anup Rao, Chris Schwiegelshohn, David P. Woodruff
2023COLTℓYi Li, Honghao Lin, David P. Woodruff
2023EuroCryptOn Differential Privacy and Adaptive Data Analysis with Bounded Space.Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou
2023FOCSStreaming Euclidean k-median and k-means with o(log n) Space.Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
2023FOCSPseudorandom Hashing for Space-bounded Computation with Applications in Streaming.Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff
2023ICLRLearning the Positions in CountSketch.Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David P. Woodruff
2023ICLRRobust Algorithms on Adaptive Inputs from Bounded Adversaries.Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou
2023ICLRAlmost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression.Alexander Munteanu, Simon Omlor, David P. Woodruff
2023ICMLImproved Algorithms for White-Box Adversarial Streams.Ying Feng, David P. Woodruff
2023ICMLFast (1+ε)-Approximation Algorithms for Binary Matrix Factorization.Ameya Velingker, Maximilian Vtsch, David P. Woodruff, Samson Zhou
2023ICMLSharper Bounds for ℓDavid P. Woodruff, Taisuke Yasuda
2023SODAThe ℓYi Li, Honghao Lin, David P. Woodruff
2023SODAOptimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time.Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou
2023SODANear-Linear Sample Complexity forRaphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou
2023SODAOnline Lewis Weight Sampling.David P. Woodruff, Taisuke Yasuda
2023STOCOptimal Eigenvalue Approximation via Sketching.William Swartworth, David P. Woodruff
2023STOCNew Subset Selection Algorithms for Low Rank Approximation: Offline and Online.David P. Woodruff, Taisuke Yasuda
2022FOCSActive Linear Regression for ℓp Norms and Beyond.Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda
2022FOCSTesting Positive Semidefiniteness Using Linear Measurements.Deanna Needell, William Swartworth, David P. Woodruff
2022FOCSHigh-Dimensional Geometric Streaming in Polynomial Space.David P. Woodruff, Taisuke Yasuda
2022ICLRTriangle and Four Cycle Counting with Predictions in Graph Streams.Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang
2022ICLRLearning-Augmented $k$-means Clustering.Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou
2022ICLRFast Regression for Structured Inputs.Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou
2022ICMLQuantum-Inspired Algorithms from Randomized Numerical Linear Algebra.Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin, David P. Woodruff
2022ICMLSketching Algorithms and Lower Bounds for Ridge Regression.Praneeth Kacham, David P. Woodruff
2022ICMLLearning Augmented Binary Search Trees.Honghao Lin, Tian Luo, David P. Woodruff
2022ICMLBounding the Width of Neural Networks via Coupled Initialization A Worst Case Analysis.Alexander Munteanu, Simon Omlor, Zhao Song, David P. Woodruff
2022ICMLLeverage Score Sampling for Tensor Product Matrices in Input Sparsity Time.David P. Woodruff, Amir Zandieh
2022PODSThe White-Box Adversarial Data Stream Model.Mikls Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou
2022PODSTruly Perfect Samplers for Data Streams and Sliding Windows.Rajesh Jayaram, David P. Woodruff, Samson Zhou
2022RECOMBA Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World.Agniva Chowdhury, Aritra Bose, Samson Zhou, David P. Woodruff, Petros Drineas
2022SODANear-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time.Nadiia Chepurko, Kenneth L. Clarkson, Praneeth Kacham, David P. Woodruff
2022SODAFrequency Estimation with One-Sided Error.Piotr Indyk, Shyam Narayanan, David P. Woodruff
2022SODAImproved Algorithms for Low Rank Approximation from Sparsity.David P. Woodruff, Taisuke Yasuda
2022STOCLow-rank approximation withAinesh Bakshi, Kenneth L. Clarkson, David P. Woodruff
2022STOCMemory bounds for the experts problem.Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou
2021COLTReduced-Rank Regression with Operator Norm Error.Praneeth Kacham, David P. Woodruff
2021COLTExponentially Improved Dimensionality Reduction for l1: Subspace Embeddings and Independence Testing.Yi Li, David P. Woodruff, Taisuke Yasuda
2021COLTAverage-Case Communication Complexity of Statistical Problems.Cyrus Rashtchian, David P. Woodruff, Peng Ye, Hanlin Zhu
2021FOCSTight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators.David P. Woodruff, Samson Zhou
2021ICALPA Very Sketchy Talk (Invited Talk).David P. Woodruff
2021ICALPSeparations for Estimating Large Frequency Moments on Data Streams.David P. Woodruff, Samson Zhou
2021ICLRLearning a Latent Simplex in Input Sparsity Time.Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou
2021ICMLFast Sketching of Polynomial Kernels of Polynomial Degree.Zhao Song, David P. Woodruff, Zheng Yu, Lichen Zhang
2021ICMLDimensionality Reduction for the Sum-of-Distances Metric.Zhili Feng, Praneeth Kacham, David P. Woodruff
2021ICMLIn-Database Regression in Input Sparsity Time.Rajesh Jayaram, Alireza Samadian, David P. Woodruff, Peng Ye
2021ICMLStreaming and Distributed Algorithms for Robust Column Subset Selection.Shuli Jiang, Dennis Li, Irene Mengze Li, Arvind V. Mahankali, David P. Woodruff
2021ICMLSingle Pass Entrywise-Transformed Low Rank Approximation.Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David P. Woodruff
2021ICMLOblivious Sketching for Logistic Regression.Alexander Munteanu, Simon Omlor, David P. Woodruff
2021PODSSubspace Exploration: Bounds on Projected Frequency Estimation.Graham Cormode, Charlie Dickens, David P. Woodruff
2021SODAOptimalArvind V. Mahankali, David P. Woodruff
2021UAINon-PSD matrix sketching with applications to regression and optimization.Zhili Feng, Fred Roosta, David P. Woodruff
2020AISTATSOptimal Deterministic Coresets for Ridge Regression.Praneeth Kacham, David P. Woodruff
2020AISTATSAutomatic Differentiation of Sketched Regression.Hang Liao, Barak A. Pearlmutter, Vamsi K. Potluru, David P. Woodruff
2020FOCSRobust and Sample Optimal Algorithms for PSD Low Rank Approximation.Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff
2020FOCSNear Optimal Linear Algebra in the Online and Sliding Window Models.Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou
2020FOCSThe Coin Problem with Applications to Data Streams.Mark Braverman, Sumegha Garg, David P. Woodruff
2020ICLRSpan Recovery for Deep Neural Networks with Applications to Input Obfuscation.Rajesh Jayaram, David P. Woodruff, Qiuyi Zhang
2020ICLRLearning-Augmented Data Stream Algorithms.Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, David P. Woodruff
2020ICMLInput-Sparsity Low Rank Approximation in Schatten Norm.Yi Li, David P. Woodruff
2020ICMLNear Input Sparsity Time Kernel Embeddings via Adaptive Sampling.David P. Woodruff, Amir Zandieh
2020PODSA Framework for Adversarially Robust Streaming Algorithms.Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev
2020WWWLSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew.Cyrus Rashtchian, Aneesh Sharma, David P. Woodruff
2020SODAOblivious Sketching of High-Degree Polynomial Kernels.Thomas D. Ahle, Michael Kapralov, Jakob Bk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh
2020SODATight Bounds for the Subspace Sketch Problem with Applications.Yi Li, Ruosong Wang, David P. Woodruff
2020SODAThe Communication Complexity of Optimization.Santosh S. Vempala, Ruosong Wang, David P. Woodruff
2020STOCNon-adaptive adaptive sampling on turnstile streams.Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou
2019AAAISublinear Time Numerical Linear Algebra for Structured Matrices.Xiaofei Shi, David P. Woodruff
2019AISTATSConditional Sparse $L_p$-norm Regression With Optimal Probability.John Hainline, Brendan Juba, Hai S. Le, David P. Woodruff
2019COLTFaster Algorithms for High-Dimensional Robust Covariance Estimation.Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff
2019COLTLearning Two Layer Rectified Neural Networks in Polynomial Time.Ainesh Bakshi, Rajesh Jayaram, David P. Woodruff
2019COLTSample-Optimal Low-Rank Approximation of Distance Matrices.Piotr Indyk, Ali Vakilian, Tal Wagner, David P. Woodruff
2019GIOn Coresets for Logistic Regression.Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff
2019ICALPRobust Communication-Optimal Distributed Clustering Algorithms.Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, David P. Woodruff
2019ICALPQuerying a Matrix Through Matrix-Vector Products.Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang
2019ICALPSeparating k-Player from t-Player One-Way Communication, with Applications to Data Streams.David P. Woodruff, Guang Yang
2019ICMLFaster Algorithms for Binary Matrix Factorization.Ravi Kumar, Rina Panigrahy, Ali Rahimi, David P. Woodruff
2019ICMLTight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-means Clustering.Taisuke Yasuda, David P. Woodruff, Manuel Fernandez
2019ICMLDimensionality Reduction for Tukey Regression.Kenneth L. Clarkson, Ruosong Wang, David P. Woodruff
2019PODSWeighted Reservoir Sampling from Distributed Streams.Rajesh Jayaram, Gokarna Sharma, Srikanta Tirthapura, David P. Woodruff
2019RECOMBSketching Algorithms for Genomic Data Analysis and Querying in a Secure Enclave.Can Kockan, Kaiyuan Zhu, Natnatee Dokmai, Nikolai Karpov, M. Oguzhan Klekci, David P. Woodruff, Sleyman Cenk Sahinalp
2019SODATesting Matrix Rank, Optimally.Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang
2019SODAA PTAS for ℓp-Low Rank Approximation.Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff
2019SODARelative Error Tensor Low Rank Approximation.Zhao Song, David P. Woodruff, Peilin Zhong
2019SODATight Bounds for ℓp Oblivious Subspace Embeddings.Ruosong Wang, David P. Woodruff
2018AISTATSSketching for Kronecker Product Regression and P-splines.Huaian Diao, Zhao Song, Wen Sun, David P. Woodruff
2018FOCSPerfect Lp Sampling in a Data Stream.Rajesh Jayaram, David P. Woodruff
2018FOCSStrong Coresets for k-Median and Subspace Approximation: Goodbye Dimension.Christian Sohler, David P. Woodruff
2018ICALPRevisiting Frequency Moment Estimation in Random Order Streams.Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang
2018ICALPHigh Probability Frequency Moment Sketches.Sumit Ganguly, David P. Woodruff
2018ICALPImproved Algorithms for Adaptive Compressed Sensing.Vasileios Nakos, Xiaofei Shi, David P. Woodruff, Hongyang Zhang
2018ICMLMatrix Norms in Data Streams: Faster, Multi-Pass and Row-Order.Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, Lin F. Yang
2018ICMLLeveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski p-Norms.Graham Cormode, Charlie Dickens, David P. Woodruff
2018KDDAn Empirical Evaluation of Sketching for Numerical Linear Algebra.Yogesh Dahiya, Dimitris Konomis, David P. Woodruff
2018PODSData Streams with Bounded Deletions.Rajesh Jayaram, David P. Woodruff
2018PODSDistributed Statistical Estimation of Matrix Products with Applications.David P. Woodruff, Qin Zhang
2017ESASketching for Geometric Problems (Invited Talk).David P. Woodruff
2017FOCSOptimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams.Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh
2017FOCSSublinear Time Low-Rank Approximation of Positive Semidefinite Matrices.Cameron Musco, David P. Woodruff
2017ICALPEmbeddings of Schatten Norms with Applications to Data Streams.Yi Li, David P. Woodruff
2017ICALPFast Regression with an $ell_infty$ Guarantee.Eric Price, Zhao Song, David P. Woodruff
2017ICMLAlgorithms for $\ell_p$ Low-Rank Approximation.Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, David P. Woodruff
2017PODSBPTree: An ℓVladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff
2017SODALow-Rank PSD Approximation in Input-Sparsity Time.Kenneth L. Clarkson, David P. Woodruff
2017SODAAdaptive Matrix Vector Product.Santosh S. Vempala, David P. Woodruff
2017STOCLow rank approximation with entrywise lZhao Song, David P. Woodruff, Peilin Zhong
2016ESAStochastic Streams: Sample Complexity vs. Space Complexity.Michael S. Crouch, Andrew McGregor, Gregory Valiant, David P. Woodruff
2016ICALPOptimal Approximate Matrix Product in Terms of Stable Rank.Michael B. Cohen, Jelani Nelson, David P. Woodruff
2016ICDEDistributed low rank approximation of implicit functions of a matrix.David P. Woodruff, Peilin Zhong
2016ICDTNew Algorithms for Heavy Hitters in Data Streams (Invited Talk).David P. Woodruff
2016ICMLHow to Fake Multiply by a Gaussian Matrix.Michael Kapralov, Vamsi K. Potluru, David P. Woodruff
2016KDDCommunication Efficient Distributed Kernel Principal Component Analysis.Maria-Florina Balcan, Yingyu Liang, Le Song, David P. Woodruff, Bo Xie
2016PODSAn Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems.Arnab Bhattacharyya, Palash Dey, David P. Woodruff
2016PODSStreaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors.Vladimir Braverman, Stephen R. Chestnut, David P. Woodruff, Lin F. Yang
2016SODANearly-optimal bounds for sparse recovery in generic norms, with applications toArturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, David P. Woodruff
2016STOCOptimal principal component analysis in distributed and streaming models.Christos Boutsidis, David P. Woodruff, Peilin Zhong
2016STOCBeating CountSketch for heavy hitters in insertion streams.Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff
2016STOCCommunication lower bounds for statistical estimation problems via a distributed data processing inequality.Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff
2016STOCOn approximating functions of the singular values in a stream.Yi Li, David P. Woodruff
2016STOCWeighted low rank approximations with provable guarantees.Ilya P. Razenshteyn, Zhao Song, David P. Woodruff
2016SPAABrief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond.Hossein Esfandiari, MohammadTaghi Hajiaghayi, David P. Woodruff
2015FOCSInput Sparsity and Hardness for Robust Subspace Approximation.Kenneth L. Clarkson, David P. Woodruff
2015ICALPAmplification of One-Way Information Complexity via Codes and Noise Sensitivity.Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev
2015ICALPThe Simultaneous Communication of Disjointness with Applications to Data Streams.Omri Weinstein, David P. Woodruff
2015PODSThe Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication.Dirk Van Gucht, Ryan Williams, David P. Woodruff, Qin Zhang
2015SODASketching forKenneth L. Clarkson, David P. Woodruff
2014COLTPrincipal Component Analysis and Higher Correlations for Distributed Data.Ravi Kannan, Santosh S. Vempala, David P. Woodruff
2014KDDImproved testing of low rank matrices.Yi Li, Zhengyu Wang, David P. Woodruff
2014PODCBeyond set disjointness: the communication complexity of finding the intersection.Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev
2014PODCSpanners and sparsifiers in dynamic streams.Michael Kapralov, David P. Woodruff
2014PODSIs min-wise hashing optimal for summarizing set intersection?Rasmus Pagh, Morten Stckel, David P. Woodruff
2014SODAOn Sketching Matrix Norms and the Top Singular Vector.Yi Li, Huy L. Nguyen, David P. Woodruff
2014SODAAn Optimal Lower Bound for Distinct Elements in the Message Passing Model.David P. Woodruff, Qin Zhang
2014STOCOptimal CUR matrix decompositions.Christos Boutsidis, David P. Woodruff
2014STOCTurnstile streaming algorithms might as well be linear sketches.Yi Li, Huy L. Nguyen, David P. Woodruff
2013COLTSubspace Embeddings and \(\ell_p\)-Regression Using Exponential Random Variables.David P. Woodruff, Qin Zhang
2013SODAThe Fast Cauchy Transform and Faster Robust Linear Regression.Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff
2013SODABeating the Direct Sum Theorem in Communication Complexity with Implications for Sketching.Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev
2013SODALower Bounds for Adaptive Sparse Recovery.Eric Price, David P. Woodruff
2013STOCLow rank approximation and regression in input sparsity time.Kenneth L. Clarkson, David P. Woodruff
2013STOCHow robust are linear sketches to adaptive inputs?Moritz Hardt, David P. Woodruff
2012ICDEA General Method for Estimating Correlated Aggregates over a Data Stream.Srikanta Tirthapura, David P. Woodruff
2012ICMLFast approximation of matrix coherence and statistical leverage.Michael W. Mahoney, Petros Drineas, Malik Magdon-Ismail, David P. Woodruff
2012ISITApplications of the Shannon-Hartley theorem to data streams and sparse recovery.Eric Price, David P. Woodruff
2012PODSSpace-efficient estimation of statistics over sub-sampled streams.Andrew McGregor, A. Pavan, Srikanta Tirthapura, David P. Woodruff
2012PODSRectangle-efficient aggregation in spatial data streams.Srikanta Tirthapura, David P. Woodruff
2012STOCTight bounds for distributed functional monitoring.David P. Woodruff, Qin Zhang
2011ESATolerant Algorithms.Rolf Klein, Rainer Penninger, Christian Sohler, David P. Woodruff
2011FOCSOn the Power of Adaptivity in Sparse Recovery.Piotr Indyk, Eric Price, David P. Woodruff
2011FOCS(1 + eps)-Approximate Sparse Recovery.Eric Price, David P. Woodruff
2011ICALPSteiner Transitive-Closure Spanners of Low-Dimensional Posets.Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
2011SODAOptimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error.T. S. Jayram, David P. Woodruff
2011STOCFast moment estimation in data streams in optimal space.Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff
2011STOCSubspace embeddings for the LChristian Sohler, David P. Woodruff
2011STOCNear-optimal private approximation protocols via a black box transformation.David P. Woodruff
2010FOCSSublinear Optimization for Machine Learning.Kenneth L. Clarkson, Elad Hazan, David P. Woodruff
2010ICALPAdditive Spanners in Nearly Quadratic Time.David P. Woodruff
2010PODSAn optimal algorithm for the distinct elements problem.Daniel M. Kane, Jelani Nelson, David P. Woodruff
2010PODSFast Manhattan sketches in data streams.Jelani Nelson, David P. Woodruff
2010SODALower Bounds for Sparse Recovery.Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff
2010SODACoresets and Sketches for High Dimensional Subspace Approximation Problems.Dan Feldman, Morteza Monemizadeh, Christian Sohler, David P. Woodruff
2010SODAOn the Exact Space Complexity of Sketching and Streaming Small Norms.Daniel M. Kane, Jelani Nelson, David P. Woodruff
2010SODA1-Pass Relative-Error LMorteza Monemizadeh, David P. Woodruff
2009FOCSEfficient Sketches for Earth-Mover Distance, with Applications.Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff
2009FOCSThe Data Stream Space Complexity of Cascaded Norms.T. S. Jayram, David P. Woodruff
2009ICDTThe average-case complexity of counting distinct elements.David P. Woodruff
2009SODATransitive-closure spanners.Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
2009STOCNumerical linear algebra in the streaming model.Kenneth L. Clarkson, David P. Woodruff
2008PODSEpistemic privacy.Alexandre V. Evfimievski, Ronald Fagin, David P. Woodruff
2007EuroCryptRevisiting the Efficiency of Malicious Two-Party Computation.David P. Woodruff
2007SODAThe communication and streaming complexity of computing the longest common and increasing subsequences.Xiaoming Sun, David P. Woodruff
2006CRYPTOFast Algorithms for the Free Riders Problem in Broadcast Encryption.Zulfikar Ramzan, David P. Woodruff
2006FOCSExplicit Exclusive Set Systems with Applications to Broadcast Encryption.Craig Gentry, Zulfikar Ramzan, David P. Woodruff
2006FOCSLower Bounds for Additive Spanners, Emulators, and More.David P. Woodruff
2006TCCPolylogarithmic Private Approximations and Efficient Matching.Piotr Indyk, David P. Woodruff
2005EuroCryptPractical Cryptography in High Dimensional Tori.Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, David P. Woodruff
2005STOCOptimal approximations of the frequency moments of data streams.Piotr Indyk, David P. Woodruff
2004CCSPrivate inference control.David P. Woodruff, Jessica Staddon
2004CRYPTOAsymptotically Optimal Communication for Torus-Based Cryptography.Marten van Dijk, David P. Woodruff
2004PODSClustering via Matrix Powering.Hanson Zhou, David P. Woodruff
2004SODAOptimal space lower bounds for all frequency moments.David P. Woodruff
2003FOCSTight Lower Bounds for the Distinct Elements Problem.Piotr Indyk, David P. Woodruff
2002EuroCryptCryptography in an Unbounded Computational Model.David P. Woodruff, Marten van Dijk