Private Streaming

My student Andre Madeira successfully defended his Phd thesis last week. Andre is culturally universal moving across countries and languages, and CS-wise broad, working on thesis at Rutgers Univ, working as an architect for secure data storage with CommVault Systems Inc, and starting now at Google Inc. in NY. Among other things in his thesis is recent work with me that initiates the study of privacy-preserving algorithms in the streaming model.

• You need a basic building block for streaming, namely, a random access to a long vector of suitable random variables, without storing all of them: we use certain pseudo-random functions to get these. The standard use of pseudorandom generators from streaming algorithms does not suffice.
  
• You also need algorithmic building blocks --- like sampling and sketching --- to base your algorithms. We show how samples with small bias suffice for functional privacy in some cases.
  

These give first known private streaming algorithms for many problems (eg., for usual suspects like L_p norm estimation), and builds on some of the earlier work of Indyk and Woodruff for privacy preserving algorithms with polylog communication (btw, this IW work deserves more attention, some nice mix of data structures and privacy preserving stuff in it).