Random Projections and Differential Privacy

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. As few applications, we show how to answer cut-queries on a graph and covariance of a matrix along a direction. This mechanism is closely related in spirit to the construction of Blocki et al. (FOCS 2012). We use a linear algebra trick that allows us to publish differentially private constant rank approximation of a matrix and uses only a single pass over the input matrix. Previous techniques, like Blum et al. (PODS 2005) and Hardt and Roth (STOC 2012), uses double pass over the input matrix.

Time remaining, we use a combinatorial observation 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.