Conference Tight bounds for distributed functional monitoring 2012 • Annual ACM Symposium on Theory of Computing • 941-960 Woodruff DP, Zhang Q
Journal Article Transitive-Closure Spanners 2012 • SIAM journal on computing (Print) • 41(6):1380-1425 Bhattacharyya A, Grigorescu E, Jung K, Raskhodnikova S, Woodruff DP
Conference $(1 +\epsilon)$-approximate Sparse Recovery 2011 • Annual Symposium on Foundations of Computer Science • 295-304 Price E, Woodruff DP
Preprint Fast approximation of matrix coherence and statistical leverage 2011 Drineas P, Magdon-Ismail M, Mahoney MW, Woodruff DP
Conference Fast moment estimation in data streams in optimal space 2011 • Annual ACM Symposium on Theory of Computing • 745-754 Kane DM, Nelson J, Porat E, Woodruff DP
Conference Near-optimal private approximation protocols via a black box transformation 2011 • Annual ACM Symposium on Theory of Computing • 735-744 Woodruff DP
Conference On the Power of Adaptivity in Sparse Recovery 2011 • Annual Symposium on Foundations of Computer Science • 285-294 Indyk P, Price E, Woodruff DP
Conference Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error 2011 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1-10 Jayram TS, Woodruff D
Conference Optimal Random Sampling from Distributed Streams Revisited 2011 • Lecture Notes in Computer Science • 6950:283-297 Tirthapura S, Woodruff DP
Conference Steiner Transitive-Closure Spanners of Low-Dimensional Posets 2011 • Lecture Notes in Computer Science • 6755:760-772 Berman P, Bhattacharyya A, Grigorescu E, Raskhodnikova S, Woodruff DP, Yaroslavtsev G
Chapter Streaming Algorithms with One-Sided Estimation 2011 • Lecture Notes in Computer Science • 6845:436-447 Brody J, Woodruff DP
Conference Subspace embeddings for the L 1 -norm with applications 2011 • Annual ACM Symposium on Theory of Computing • 755-764 Sohler C, Woodruff DP
Chapter Tolerant Algorithms 2011 • Lecture Notes in Computer Science • 6942:736-747 Klein R, Penninger R, Sohler C, Woodruff DP
Conference 1-Pass Relative-Error L p -Sampling with Applications 2010 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1143-1160 Monemizadeh M, Woodruff DP
Chapter A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field 2010 • Lecture Notes in Computer Science • 6302:766-779 Woodruff DP
Chapter Additive Spanners in Nearly Quadratic Time 2010 • Lecture Notes in Computer Science • 6198:463-474 Woodruff DP
Conference An optimal algorithm for the distinct elements problem 2010 • Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems • 41-52 Kane DM, Nelson J, Woodruff DP
Conference Coresets and Sketches for High Dimensional Subspace Approximation Problems 2010 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 630-649 Feldman D, Monemizadeh M, Sohler C, Woodruff DP
Journal Article Epistemic privacy 2010 • Journal of the ACM • 58(1):1-45 Evfimievski A, Fagin R, Woodruff D
Conference Fast Manhattan sketches in data streams 2010 • Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems • 99-110 Nelson J, Woodruff DP
Preprint Fast Moment Estimation in Data Streams in Optimal Space 2010 Kane DM, Nelson J, Porat E, Woodruff DP
Chapter Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners 2010 • Lecture Notes in Computer Science • 6302:448-461 Bhattacharyya A, Grigorescu E, Jha M, Jung K, Raskhodnikova S, Woodruff DP
Conference Lower Bounds for Sparse Recovery 2010 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1190-1197 Ba KD, Indyk P, Price E, Woodruff DP
Conference On the Exact Space Complexity of Sketching and Streaming Small Norms 2010 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1161-1178 Kane DM, Nelson J, Woodruff DP
