Dartmouth Events

Abstract:

Differential privacy (DP) is a rigorous mathematical definition of privacy and has recently been adopted by industry and government entities alike. Informally an algorithm that takes a dataset as input is said to be differentially private if one cannot tell whether an individual's data was included in the original dataset or not, simply by looking at the output of the algorithm. While there are many techniques for transforming non-DP algorithms that exactly compute functions into DP algorithms, developing such transformations in the case of algorithms that approximate functions of interest is less understood.   

In this talk, we present a framework for efficiently transforming certain approximation algorithms into differentially-private variants, in a black-box manner. We show that a specific class of algorithms which we call ``tunable approximation algorithms'' can be made differentially private without sacrificing accuracy, as long as the function being approximated by the algorithm has small ``global sensitivity''.
Our framework naturally applies to transform non-private FPRAS and FPTAS algorithms into ϵ-DP approximation algorithms where the former case requires an additional postprocessing step. We apply our framework in the context of sublinear-time  and sublinear-space algorithms, while preserving the nature of the algorithm in meaningful ranges of the parameters. Our results include the first (to the best of our knowledge) ϵ-edge DP sublinear-time algorithm for estimating the number of triangles, the number of connected components, and the weight of a minimum spanning tree of a graph. In the area of streaming algorithms, our results include ϵ-DP algorithms for estimating Lp-norms, distinct elements, and weighted minimum spanning tree for both insertion-only and turnstile streams. Our transformation also provides a private version of the smooth histogram framework, which is commonly used for converting streaming algorithms into sliding window variants, and achieves a multiplicative approximation to many problems, such as estimating Lp-norms, distinct elements, nad the length of the longest increasing subsequence.

Bio:

Tamalika's research interests are in data privacy and theoretical computer science. Specifically she is interested in designing super-efficient differentially private algorithms in resource constrained settings where the resource can be time or space. Her research also encompasses the interplay of differential privacy with social science, law and policy.

Tamalika completed her Ph.D. in Computer Science from Purdue University where she received the Bilsland Dissertation Fellowship for her dissertation studies.