Seminar by Jalaj Upadhyay
Random Projections and Differential Privacy
Jalaj Upadhyay
University of Waterloo, Ontario
Date: Monday, January 13th, 2014
Time: 15:30 PM
Venue: CS101.Abstract:
In this talk, we consider the efficiency aspects of the mechanisms for differential privacy, i.e., the run-time and the sampling complexity of mechanism design.
In the first part of the talk, we consider the problem of run-time efficient mechanisms. We adapt the technique of Blocki et al. (FOCS 2012) to preserve differential privacy for answering cut-queries on sparse graphs with a much efficient sanitizer. We then use this as the base technique to construct an efficient sanitizer for arbitrary graphs. In particular, we precondition the graph by standard sparsification techniques and then apply our basic sanitizer. In this respect, our approach is complementary to the Gupta, Roth, and Ullman's Randomized Response mechanism (TCC 2012) for answering cut queries.
In the second part of the talk, we present a non-interactive multiplicative mechanism that uses O(n) samples from Bernoulli and Gaussian distribution, and answer queries that are in the form of Euclidean norm of some function of the data-base. We use a linear algebra trick that allows us to publish differentially private low rank approximation of a matrix using only a single pass over the input matrix. Previous techniques, like Blum et al. (PODS 2005) and Hardt and Roth (STOC 2012, STOC 2013), uses multiple passes over the input matrix.
Time remaining, we give a combinatorial argument to argue that our mechanisms can also answer (S,T)-cut queries with the same guarantees in terms of efficiency, utility, and differential privacy. Moreover, we achieve a better utility guarantee than Gupta, Roth, and Ullman (TCC 2012). As a conclusion, we suggest further optimization by showing that fast Johnson-Lindenstrauss transform of Ailon and Chazelle (SIAM J. of Computing 2009) also preserves differential privacy.
Part of this work appeared in ASIACRYPT, 2013.
About the speaker:
Jalaj Upadhyay is a PhD student working with Douglas Stinson at University of Waterloo.