ABSTRACT: The framework of differential privacy allows one to answer global queries about information in a database while protecting privacy specific to individuals whose information it contains. There are many known differentially private algorithms for specific queries and classes of queries. What if database analysts are allowed to write their own programs to access a private database? Can one test if such programs are differentially private? Can one ensure that they are differentially private?
In this talk, we will show that these questions are related to algorithmic questions about a basic property of functions: the Lipschitz property. The Lipschitz property is defined as follows: a real-valued function f that takes a vector x is Lipschitz if for all pairs of inputs x and y, the value |f(x)-f(y)| is at most the number of coordinates on which x and y differ. We will discuss sublinear-time algorithms for testing whether a function is Lipschitz and for reconstructing Lipschitz functions.
*The talk is based on joint works with Madhav Jha, with Pranjal Awasthi, Madhav Jha and Marco Molinaro, and with Kashyap Dixit, Madhav Jha and Abhradeep Thakurta.