David P. Woodruff Research Staff Member IBM Almaden Research Center Computer Science Principles and Methodologies Department

2012

• ICML, Fast approximation of matrix coherence and statistical leverage (to appear). Full version on arXiv
  (with Petros Drineas, Malik Magdon-Ismail, and Michael Mahoney)
• SSP, Reusable Low-Error Compressive Sampling Schemes Through Privacy (to appear)
  (with Anna Gilbert, Brett Hemenway, Martin Strauss, and Mary Wootters)
• ISIT, Applications of the Shannon-Hartley Theorem to Data Streams and Sparse Recovery (to appear)
  (with Eric Price)
• PODS, Rectangle-Efficient Aggregation in Spatial Data Streams pdf
  (with Srikanta Tirthapura)
• PODS, Space-Efficient Estimation of Statistics over Sub-Sampled Streams pdf
  (with Andrew McGregor, A. Pavan, and Srikanta Tirthapura)
• STOC, Tight Bounds for Distributed Functional Monitoring pdf . Earlier full version on arXiv
  (with Qin Zhang)
  
• ICDE, A General Method for Estimating Correlated Aggregates over a Data Stream pdf
  (with Srikanta Tirthapura)
  

2011

• FOCS, (1+eps)-Approximate Sparse Recovery pdf
  (with Eric Price)
  Talk: .ppt
  
• FOCS, On the Power of Adaptivity in Sparse Recovery pdf
  (with Piotr Indyk and Eric Price)
  
• DISC, Optimal Random Sampling from Distributed Streams Revisited pdf
  (with Srikanta Tirthapura)
  
• ESA, Tolerant Algorithms pdf
  (with Rolf Klein, Rainer Penninger, and Christian Sohler)
  
• RANDOM, Streaming Algorithms with One-Sided Estimation pdf
  (with Joshua Brody)
  
• ICALP, Linear Programming and Combinatorial Bounds on Steiner Transitive-Closure Spanners pdf . Full version on arXiv
  (with Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, and Grigory Yaroslavtsev)
  
• STOC, Near-Optimal Private Approximation Protocols via a Black Box Transformation pdf
  Talk: .ppt
  
• STOC, Subspace Embeddings for the L_1-norm with Applications pdf
  (with Christian Sohler)
  Talk: .ppt
  
• STOC, Fast Moment Estimation in Data Streams in Optimal Space pdf , Full version on ArXiv
  (with Daniel M. Kane, Jelani Nelson, and Ely Porat)
  Talk: .ppt
  
• ICS, The Complexity of Linear Dependence Problems in Vector Spaces pdf
  (with Arnab Bhattacharyya, Piotr Indyk, and Ning Xie)
  Talk: .ppt
  
• SODA, Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Low Error pdf
  Invited to the special issue for Soda, 2011 in Transactions on Algorithms. Full version in preparation.
  (with T.S. Jayram)
  Talk: .ppt

2010

• FOCS, Sublinear Optimization for Machine Learning. Short version: pdf , Full version on ArXiv
  (with Ken Clarkson and Elad Hazan)
  Talk: .ppt
  
• RANDOM, A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field pdf
  Talk: .ppt
  
• RANDOM, Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners Conference version: pdf
  Draft of Full version: pdf
  (with Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, and Sofya Raskhodnikova)
  
• ICALP, Additive Spanners in Nearly Quadratic Time pdf
  Talk: .ppt
  
• PODS, An Optimal Algorithm for the Distinct Elements Problem pdf
  PODS Best Paper Award
  Pat Goldberg Best Paper Award
  Invited to Journal of the ACM, preliminary full version: pdf
  (with Daniel M. Kane and Jelani Nelson)
  Long Talk: .ppt Short Talk: .ppt
  
• PODS, Fast Manhattan Sketches in Data Streams pdf
  (with Jelani Nelson)
  
• 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)
  Talk: .ppt

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)
  Talk: .ppt
  
• 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: .ppt

2008

• PODS, Epistemic Privacy ps, pdf ,
  Journal of the ACM, full version: pdf
  (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

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