[Theory] UC Theory Seminar

[Alexander Razborov]

Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar

Tuesday, November 5
Ry 251 @3:30pm

Aleksandar Nikolov
Stanford University

Title: The Power of Factorization

Abstract: A central goal in private data analysis is to estimate 
statistics about an unknown distribution from a dataset possibly 
containing sensitive information, so that the privacy of any individual 
represented in the dataset is preserved. We study this question in the 
model of non-interactive local differential privacy (LDP), in which 
every person in the dataset randomizes their own data in order to 
preserve its privacy, before sending it to a central server. We give a 
characterization of the minimum number of samples necessary to get an 
accurate estimates of a given set of statistical queries, as well as a 
characterization of the sample complexity of agnostic PAC learning in 
this model. The characterization is tight up polylogarithmic factors for 
any given set of statistical queries, and, respectively, any given 
concept class. The characterization is achieved by a simple and 
efficient instance-optimal (with respect to the queries/concept class) 
approximate factorization mechanism, i.e. a mechanism that answers the 
statistical queries by answering a different set of strategy queries, 
from which the answers to the original queries can be approximately 
reconstructed.

Based on joint work with Alexander Edmonds and Jonathan Ullman


Refreshments will be served prior to the talk at 3:15 pm Ry 257