7. TwoParty Differential Privacy and Deterministic Extraction from SanthaVazirani Sources (Г. Ярославцев, Pennsylvania State University) (Sunday, December 19, 2010  17:20  18:55)
The talk presents recent results (from a paper at FOCS 2010) on "differential privacy" in a distributed setting: two parties holding sensitive data would like to analyze the union of their data sets while preserving the privacy of the individuals whose data they hold.
The paper gives almost tight bounds on the accuracy of such analysis for the Hamming distance function. These bounds show the contrast between information theoretic and computational differential privacy in the twoparty setting and also between the twoparty and the clientserver setting. The proof technique introduces a connection between differential privacy and deterministic extraction from independent SanthaVazirani sources.
The talk is mostly based on the paper "The Limits of TwoParty Differential Privacy" by Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar and Salil Vadhan (http://research.microsoft.com/apps/pubs/default.aspx?id=137029).
Basic background knowledge of information theory and probability theory can be useful.
http://www.lektorium.tv/lecture/?id=13175
