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.