40 citations · 222 across the 36 of their papers we have counts for
7 papers · 1 filter
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs
AmirMahdi Ahmadinejad, John Peebles, Edward Pyne +2
In this paper, we introduce a new, spectral notion of approximation between directed graphs, which we call singular value (SV) approximation. SV-approximation is stronger than prev…
Concurrent Composition Theorems for Differential Privacy
Salil Vadhan, Wanrong Zhang
We study the concurrent composition properties of interactive differentially private mechanisms, whereby an adversary can arbitrarily interleave its queries to the different mechan…
Spectral Sparsification via Bounded-Independence Sampling
Dean Doron, Jack Murtagh, Salil Vadhan +1
We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph on vertices described…
Differential Privacy on Finite Computers
Victor Balcer, Salil Vadhan
We consider the problem of designing and analyzing differentially private algorithms that can be implemented on {\em discrete} models of computation in {\em strict} polynomial time…
Locating a Small Cluster Privately
Kobbi Nissim, Uri Stemmer, Salil Vadhan
We present a new algorithm for locating a small cluster of points with differential privacy [Dwork, McSherry, Nissim, and Smith, 2006]. Our algorithm has implications to private da…
Faster Algorithms for Privately Releasing Marginals
Justin Thaler, Jonathan Ullman, Salil Vadhan
We study the problem of releasing -way marginals of a database , while preserving differential privacy. The answer to a -way marginal query is the fracti…