Technion Computer Science Colloquium GUEST TALK. Note unusual hour on Thursday 07/04/2011 Time+Place : Thursday 07/04/2011 15:00 room 337-8 Taub Bld. Speaker : David Woodruff SPECIAL GUEST TALK. Note unusual hour Affiliation: IBM Almaden Host : Yuval Ishai Title : Near-Optimal Private Approximation Protocols via a Black Box Transformation Abstract : A private approximation of a function f is defined to be another function that approximates f in the usual sense, but does not reveal any information about its input other than what can be deduced from knowing the exact function value f. In general it is insufficient to use generic techniques in cryptography to design private approximations from non-private approximations. This is because, somewhat counterintuitively, the approximation may reveal more information about the input than what the exact function value reveals about the input. For example, the least-significant bit of a +- 1 approximation to the Hamming distance between two input vectors may be set to equal a particular bit of an input vector. We show the following general transformation: any two-party protocol for outputting a (1+eps)-approximation to f(x,y) = sum_{j=1}^n g(x_j, y_j) with constant probability, for any non-negative efficiently computable function g, can be transformed into a two-party private approximation protocol with only a polylogarithmic factor loss in communication, computation, and round complexity. Applying our transformation and variations of it, we obtain near-optimal private approximation protocols for a wide range of problems in the data stream literature for which previously nothing was known. To appear in STOC, 2011. Short Bio: David Woodruff did his B.S. degrees in mathematics and computer science, and his Ph.D. in theoretical computer science, each at MIT. His advisor was Piotr Indyk. He graduated in 2007 and joined the theory group at IBM Almaden as a Research Staff Member, where he has been ever since. ---------------------------------------------------------- Visit our home page- <http://www.cs.technion.ac.il/~colloq> --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Hadas Heier <heier@cs.technion.ac.il>