40 citations · 222 across the 36 of their papers we have counts for
3 papers · 1 filter
Inaccessible Entropy I: Inaccessible Entropy Generators and Statistically Hiding Commitments from One-Way Functions
Iftach Haitner, Omer Reingold, Salil Vadhan +1
We put forth a new computational notion of entropy, measuring the (in)feasibility of sampling high-entropy strings that are consistent with a given generator. Specifically, the i't…
Differentially Private Simple Linear Regression
Daniel Alabi, Audra McMillan, Jayshree Sarathy +2
Economics and social science research often require analyzing datasets of sensitive personal information at fine granularity, with models fit to small subsets of the data. Unfortun…
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…