David P. Woodruff

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

Eric Price, David P. Woodruff: Lower Bounds for Adaptive Sparse Recovery. SODA 2013: 652-663

Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev: Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching. SODA 2013: 1738-1756

David P. Woodruff, Grigory Yaroslavtsev: The Round Complexity of Small Set Intersection. CoRR abs/1304.1796 (2013)

David P. Woodruff, Qin Zhang: When Distributed Computation does not Help. CoRR abs/1304.4636 (2013)

Kenneth L. Clarkson, Elad Hazan, David P. Woodruff: Sublinear optimization for machine learning. J. ACM 59(5): 23 (2012)

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)

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff: Transitive-Closure Spanners. SIAM J. Comput. 41(6): 1380-1425 (2012)

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. Discrete Math. 26(2): 618-646 (2012)

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

Srikanta Tirthapura, David P. Woodruff: A General Method for Estimating Correlated Aggregates over a Data Stream. ICDE 2012: 162-173

Michael W. Mahoney, Petros Drineas, Malik Magdon-Ismail, David P. Woodruff: Fast approximation of matrix coherence and statistical leverage. ICML 2012

Eric Price, David P. Woodruff: Applications of the Shannon-Hartley theorem to data streams and sparse recovery. ISIT 2012: 2446-2450

Andrew McGregor, A. Pavan, Srikanta Tirthapura, David P. Woodruff: Space-efficient estimation of statistics over sub-sampled streams. PODS 2012: 273-282

Srikanta Tirthapura, David P. Woodruff: Rectangle-efficient aggregation in spatial data streams. PODS 2012: 283-294

David P. Woodruff, Qin Zhang: Tight bounds for distributed functional monitoring. STOC 2012: 941-960

Eric Price, David P. Woodruff: Lower Bounds for Adaptive Sparse Recovery. CoRR abs/1205.3518 (2012)

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)

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)

Kenneth L. Clarkson, David P. Woodruff: Low Rank Approximation and Regression in Input Sparsity Time. CoRR abs/1207.6365 (2012)

Moritz Hardt, David P. Woodruff: How Robust are Linear Sketches to Adaptive Inputs? CoRR abs/1211.1056 (2012)

Joshua Brody, David P. Woodruff: Streaming Algorithms with One-Sided Estimation. APPROX-RANDOM 2011: 436-447

Rolf Klein, Rainer Penninger, Christian Sohler, David P. Woodruff: Tolerant Algorithms. ESA 2011: 736-747

Piotr Indyk, Eric Price, David P. Woodruff: On the Power of Adaptivity in Sparse Recovery. FOCS 2011: 285-294

Eric Price, David P. Woodruff: (1 + eps)-Approximate Sparse Recovery. FOCS 2011: 295-304

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

Arnab Bhattacharyya, Piotr Indyk, David P. Woodruff, Ning Xie: The Complexity of Linear Dependence Problems in Vector Spaces. ICS 2011: 496-508

T. S. Jayram, David P. Woodruff: Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error. SODA 2011: 1-10

David P. Woodruff: Near-optimal private approximation protocols via a black box transformation. STOC 2011: 735-744

Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff: Fast moment estimation in data streams in optimal space. STOC 2011: 745-754

Christian Sohler, David P. Woodruff: Subspace embeddings for the L₁-norm with applications. STOC 2011: 755-764

Srikanta Tirthapura, David P. Woodruff: Optimal Random Sampling from Distributed Streams Revisited. DISC 2011: 283-297

Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff: Lower Bounds for Sparse Recovery. CoRR abs/1106.0365 (2011)

Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff: Fast approximation of matrix coherence and statistical leverage. CoRR abs/1109.3843 (2011)

Piotr Indyk, Eric Price, David P. Woodruff: On the Power of Adaptivity in Sparse Recovery. CoRR abs/1110.3850 (2011)

Eric Price, David P. Woodruff: (1+eps)-approximate Sparse Recovery. CoRR abs/1110.4414 (2011)

David P. Woodruff, Qin Zhang: Tight Bounds for Distributed Functional Monitoring. CoRR abs/1112.5153 (2011)

Alexandre V. Evfimievski, Ronald Fagin, David P. Woodruff: Epistemic privacy. J. ACM 58(1): 2 (2010)

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

David P. Woodruff: A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. APPROX-RANDOM 2010: 766-779

Kenneth L. Clarkson, Elad Hazan, David P. Woodruff: Sublinear Optimization for Machine Learning. FOCS 2010: 449-457

David P. Woodruff: Additive Spanners in Nearly Quadratic Time. ICALP (1) 2010: 463-474

Daniel M. Kane, Jelani Nelson, David P. Woodruff: An optimal algorithm for the distinct elements problem. PODS 2010: 41-52

Jelani Nelson, David P. Woodruff: Fast Manhattan sketches in data streams. PODS 2010: 99-110

Dan Feldman, Morteza Monemizadeh, Christian Sohler, David P. Woodruff: Coresets and Sketches for High Dimensional Subspace Approximation Problems. SODA 2010: 630-649

Morteza Monemizadeh, David P. Woodruff: 1-Pass Relative-Error L_p-Sampling with Applications. SODA 2010: 1143-1160

Daniel M. Kane, Jelani Nelson, David P. Woodruff: On the Exact Space Complexity of Sketching and Streaming Small Norms. SODA 2010: 1161-1178

Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff: Lower Bounds for Sparse Recovery. SODA 2010: 1190-1197

Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff: Fast Moment Estimation in Data Streams in Optimal Space. CoRR abs/1007.4191 (2010)

Kenneth L. Clarkson, Elad Hazan, David P. Woodruff: Sublinear Optimization for Machine Learning. CoRR abs/1010.4408 (2010)

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)

Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff: Efficient Sketches for Earth-Mover Distance, with Applications. FOCS 2009: 324-330

T. S. Jayram, David P. Woodruff: The Data Stream Space Complexity of Cascaded Norms. FOCS 2009: 765-774

David P. Woodruff: The average-case complexity of counting distinct elements. ICDT 2009: 284-295

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff: Transitive-closure spanners. SODA 2009: 932-941

Kenneth L. Clarkson, David P. Woodruff: Numerical linear algebra in the streaming model. STOC 2009: 205-214

David P. Woodruff: Frequency Moments. Encyclopedia of Database Systems 2009: 1169-1170

Jelani Nelson, David P. Woodruff: A Near-Optimal Algorithm for L1-Difference. CoRR abs/0904.2027 (2009)

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff: Transitive-Closure Spanners of the Hypercube and the Hypergrid. Electronic Colloquium on Computational Complexity (ECCC) 16: 46 (2009)

David P. Woodruff: Corruption and Recovery-Efficient Locally Decodable Codes. APPROX-RANDOM 2008: 584-595

Alexandre V. Evfimievski, Ronald Fagin, David P. Woodruff: Epistemic privacy. PODS 2008: 171-180

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff: Transitive-Closure Spanners. CoRR abs/0808.1787 (2008)

Jelani Nelson, David P. Woodruff: Revisiting Norm Estimation in Data Streams. CoRR abs/0811.3648 (2008)

David P. Woodruff, Sergey Yekhanin: A Geometric Approach to Information-Theoretic Private Information Retrieval. SIAM J. Comput. 37(4): 1046-1056 (2007)

David P. Woodruff: Revisiting the Efficiency of Malicious Two-Party Computation. EUROCRYPT 2007: 79-96

Xiaoming Sun, David P. Woodruff: The communication and streaming complexity of computing the longest common and increasing subsequences. SODA 2007: 336-345

David P. Woodruff: New Lower Bounds for General Locally Decodable Codes. Electronic Colloquium on Computational Complexity (ECCC) 14(006) (2007)

David P. Woodruff: Better Approximations for the Minimum Common Integer Partition Problem. APPROX-RANDOM 2006: 248-259

Zulfikar Ramzan, David P. Woodruff: Fast Algorithms for the Free Riders Problem in Broadcast Encryption. CRYPTO 2006: 308-325

Craig Gentry, Zulfikar Ramzan, David P. Woodruff: Explicit Exclusive Set Systems with Applications to Broadcast Encryption. FOCS 2006: 27-38

David P. Woodruff: Lower Bounds for Additive Spanners, Emulators, and More. FOCS 2006: 389-398

Piotr Indyk, David P. Woodruff: Polylogarithmic Private Approximations and Efficient Matching. TCC 2006: 245-264

Zulfikar Ramzan, David P. Woodruff: Fast Algorithms for the Free Riders Problem in Broadcast Encryption. IACR Cryptology ePrint Archive 2006: 293 (2006)

David P. Woodruff: Revisiting the Efficiency of Malicious Two-Party Computation. IACR Cryptology ePrint Archive 2006: 397 (2006)

David P. Woodruff, Sergey Yekhanin: A Geometric Approach to Information-Theoretic Private Information Retrieval. IEEE Conference on Computational Complexity 2005: 275-284

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

Piotr Indyk, David P. Woodruff: Optimal approximations of the frequency moments of data streams. STOC 2005: 202-208

David P. Woodruff, Sergey Yekhanin: A Geometric Approach to Information-Theoretic Private Information Retrieval. Electronic Colloquium on Computational Complexity (ECCC)(009) (2005)

Piotr Indyk, David P. Woodruff: Polylogarithmic Private Approximations and Efficient Matching. Electronic Colloquium on Computational Complexity (ECCC)(117) (2005)

David P. Woodruff, Jessica Staddon: Private inference control. ACM Conference on Computer and Communications Security 2004: 188-197

Marten van Dijk, David P. Woodruff: Asymptotically Optimal Communication for Torus-Based Cryptography. CRYPTO 2004: 157-178

Hanson Zhou, David P. Woodruff: Clustering via Matrix Powering. PODS 2004: 136-142

David P. Woodruff: Optimal space lower bounds for all frequency moments. SODA 2004: 167-175

David P. Woodruff, Jessica Staddon: Private Inference Control. IACR Cryptology ePrint Archive 2004: 130 (2004)

Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, David P. Woodruff: Practical Cryptography in High Dimensional Tori. IACR Cryptology ePrint Archive 2004: 352 (2004)

Piotr Indyk, David P. Woodruff: Tight Lower Bounds for the Distinct Elements Problem. FOCS 2003: 283-288

David P. Woodruff, Marten van Dijk: Cryptography in an Unbounded Computational Model. EUROCRYPT 2002: 149-164