Chapter A quadratic lower bound for three-query linear locally decodable codes over any field 2010 • Lecture Notes in Computer Science • 6302 LNCS:766-779 Woodruff DP
Chapter Additive spanners in nearly quadratic time 2010 • Lecture Notes in Computer Science • 6198 LNCS(PART 1):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): 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-109 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 LNCS: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
Preprint Steiner Transitive-Closure Spanners of d-Dimensional Posets 2010 Berman P, Bhattacharyya A, Grigorescu E, Raskhodnikova S, Woodruff D, Yaroslavtsev G
Conference Sublinear optimization for machine learning 2010 • Annual Symposium on Foundations of Computer Science • 449-457 Clarkson KL, Hazan E, Woodruff DP
Conference Efficient sketches for Earth-Mover Distance, with applications 2009 • Annual Symposium on Foundations of Computer Science • 324-330 Andoni A, Ba KD, Indyk P, Woodruff D
Conference Numerical linear algebra in the streaming model 2009 • Annual ACM Symposium on Theory of Computing • 205-214 Clarkson KL, Woodruff DP
Conference The average-case complexity of counting distinct elements 2009 • ACM International Conference Proceeding Series • 361:284-295 Woodruff DP
Conference The data stream space complexity of cascaded norms 2009 • Annual Symposium on Foundations of Computer Science • 765-774 Jayram TS, Woodruff DP
Conference Transitive-closure spanners 2009 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 932-941 Bhattacharyya A, Grigorescu E, Jung K, Raskhodnikova S, Woodruff DP
Conference Corruption and recovery-efficient locally decodable codes 2008 • Lecture Notes in Computer Science • 5171 LNCS:584-595 Woodruff D
Conference Epistemic privacy 2008 • Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems • 171-180 Evfimievski A, Fagin R, Woodruff D
Preprint Transitive-Closure Spanners 2008 Bhattacharyya A, Grigorescu E, Jung K, Raskhodnikova S, Woodruff DP
Journal Article A Geometric approach to information-theoretic private information retrieval 2007 • SIAM journal on computing (Print) • 37(4):1046-1056 Woodruff D, Yekhanin S
Chapter Revisiting the efficiency of malicious two-party computation 2007 • Lecture Notes in Computer Science • 4515 LNCS:79-96 Woodruff DP
Conference The communication and streaming complexity of computing the longest common and increasing subsequences 2007 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 07-09-January-2007:336-345 Sun X, Woodruff DP
