I did my Ph.D. at MIT in theoretical computer science. I was very fortunate to have Piotr Indyk as my advisor and to to spend a year at Tsinghua University under the supervision of Andy Yao . My main interests are algorithms, complexity theory, and cryptography.
Contact: You can email either dpwood (at) alum (dot) mit (dot) edu or the address dpwoodru (at) us (dot) ibm (dot) com
Copyright: Persons copying the material below should adhere to the terms of each author's copyright.
CV: pdf (out of date)
Program Committees
2010
- SODA, Coresets and Sketches for High Dimensional Subspace Approximation Problems pdf
(with Dan Feldman, Morteza Monemizadeh, and Christian Sohler)
- SODA, Lower Bounds for Sparse Recovery pdf
(with Khanh Do Ba, Piotr Indyk, and Eric Price)
- SODA, On the Exact Space Complexity of Sketching and Streaming Small Norms pdf
(with Daniel M. Kane and Jelani Nelson)
- SODA, 1-pass Relative-Error L_p-Sampling with Applications pdf
(with Morteza Monemizadeh)
2009
- FOCS, The Data Stream Space Complexity of Cascaded Norms pdf
(with T.S. Jayram)
Talk: .ppt
- FOCS, Efficient Sketches for Earth-Mover Distances, with Applications pdf
(with Alex Andoni, Khanh Do Ba, and Piotr Indyk)
- STOC, Numerical Linear Algebra in the Streaming Model (full version)
pdf
(with Ken Clarkson)
Talk: .ppt Longer .ppt
- ICDT, The Average Case Complexity of Counting Distinct Elements pdf
Talk .ppt
- SODA, Transitive-Closure Spanners. Full version on ArXiv
(with Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, and Sofya Raskhodnikova)
Talk (slides jointly made with coauthors): .ppt
2008
- PODS, Epistemic Privacy ps, pdf , invited to JACM (in submission)
(with Alexandre Evfimievski and Ron Fagin)
- RANDOM, Corruption and Recovery-Efficient Locally Decodable Codes (extended abstract) pdf
Talk: .ppt
2007
- Ph.D. Thesis, Efficient and Private Distance Approximation in the Communication and Streaming Models ps pdf
This thesis contains results from the papers "Optimal Approximations of the Frequency Moments", "Private Polylogarithmic Approximations and Efficient Matching", "Optimal Space Lower Bounds for all Frequency Moments", and "Tight Lower Bounds for the Distinct Elements Problem". It serves as a better and more thorough exposition of these papers.
- New Lower Bounds for General Locally Decodable Codes ECCC link
- Invited article in the Encyclopedia of Database Systems, Frequency Moments pdf
- Eurocrypt, Revisiting the Efficiency of Malicious Two-Party Computation eprint link
Talk: .ppt
- SODA, The Communication and Streaming Complexity of Computing the Longest Common and Increasing Subsequences ps, pdf
(with Xiaoming Sun)
Talk: .ppt
2006
- FOCS, Lower Bounds for Additive Spanners, Emulators, and More
ps, pdf
Long talk: .ppt , FOCS talk: ppt
- FOCS, Explicit Exclusive Set Systems with Applications to Broadcast Encryption
ps, pdf
(with Craig Gentry, Zulfikar Ramzan)
Long Talk: .ppt Crypto rump session Talk: .ppt , FOCS talk: ppt
- Crypto, Fast Algorithms for the Free Riders Problem in Broadcast Encryption ps, pdf Full version on eprint eprint
(with Zulfikar Ramzan)
Talk: .ppt
- APPROX, Better Approximations for the Minimum Common Integer Partition Problem ps, pdf
Talk: .ppt
- TCC, Private Polylogarithmic Approximations and Efficient Matching. Also, ECCC ps, pdf Conference version (with some edits) ps, pdf
(with Piotr Indyk)
Talk: long .ppt and short .ppt
Also see my Ph.D. thesis.
2005
- STOC, Optimal Approximations of the Frequency Moments of Data Streams (some typos fixed) ps, pdf
(with Piotr Indyk)
Talk: .ppt
Also see my Ph.D. thesis.
- Eurocrypt, Practical Cryptography in High Dimensional Tori. Available: eprint
(with Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam)
Talk: .ppt
- CCC, to appear in SICOMP, A Geometric Approach to Information-theoretic Private Information Retrieval. Also, ECCC ps, pdf
Conference version: pdf
(with Sergey Yekhanin)
2004
- SODA, Optimal Space Lower Bounds for all Frequency Moments, revised ps, conf pdf
Talk: short .ppt and long .ppt
Also see my Ph.D. thesis.
- PODS, Clustering via Matrix Powering, ps, pdf
Also, a note clarifying the algorithm txt
Thanks to Ding Bolin for pointing this out.
(with Hanson Zhou)
- Crypto, Asymptotically Optimal Communication for Torus-Based Cryptography, ps, pdf
(with Marten van Dijk)
Talk: .ppt
- CCS, Private Inference Control. Conference version: ps, Long version available: IACR eprint
(with Jessica Staddon)
Talk: Dimacs/Portia Privacy-Preserving workshop: .ppt, conf: .ppt
2003
- FOCS, Tight Lower Bounds for the Distinct Elements Problem, revised ps, conf pdf
(with Piotr Indyk)
Talk: (Also DIMACS Embeddings workshop) .ppt
Also see my Ph.D. thesis.
2002
- Eurocrypt, Cryptography in an Unbounded Computational Model, ps, pdf
(with Marten van Dijk)
Talk: .pdf
Conference Versions
DBLP
Miscellaneous Papers
- Master's thesis (based on Eurocrypt 2002) ps, pdf
- Survey on stream-computing F_0 ps, pdf
(with Johnny Chen, Naveen Sunkavalley)
Privacy
|
Legal
|
Contact
|
IBM Home |
Research
Home |
Project
List |
Research
Sites
