Publications by David Woodruff

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

Steiner Transitive-Closure Spanners of Low-Dimensional Posets

2011 • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) • 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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) • 6845:436-447
Brody J, Woodruff DP

Chapter

Tolerant Algorithms

2011 • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) • 6942:736-747
Klein R, Penninger R, Sohler C, Woodruff DP

Chapter

Additive Spanners in Nearly Quadratic Time

2010 • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) • 6198:463-474
Woodruff DP

Journal Article

Epistemic privacy

2010 • Journal of the ACM • 58(1):1-45
Evfimievski A, Fagin R, Woodruff D