12 citations · 21 across the 5 of their papers we have counts for
5 papers
Private Query Release via the Johnson-Lindenstrauss Transform
Aleksandar Nikolov
We introduce a new method for releasing answers to statistical queries with differential privacy, based on the Johnson-Lindenstrauss lemma. The key idea is to randomly project the…
Lower Bounds for Differential Privacy from Gaussian Width
Assimakis Kattis, Aleksandar Nikolov
We study the optimal sample complexity of a given workload of linear queries under the constraints of differential privacy. The sample complexity of a query answering mechanism und…
Optimal Private Halfspace Counting via Discrepancy
S. Muthukrishnan, Aleksandar Nikolov
A range counting problem is specified by a set of size of points in , an integer weight associated to each point , and a range space ${\c…
Pan-private Algorithms: When Memory Does Not Help
Darakhshan Mir, S. Muthukrishnan, Aleksandar Nikolov +1
Consider updates arriving online in which the th input is , where 's are thought of as IDs of users. Informally, a randomized function is {\em differentially…
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
Prahladh Harsha, Moses Charikar, Matthew Andrews +14
These are the lecture notes for the DIMACS Tutorial "Limits of Approximation Algorithms: PCPs and Unique Games" held at the DIMACS Center, CoRE Building, Rutgers University on 20-2…