11 citations · 22 across the 8 of their papers we have counts for
15 papers
Learning versus Refutation in Noninteractive Local Differential Privacy
Alexander Edmonds, Aleksandar Nikolov, Toniann Pitassi
We study two basic statistical tasks in non-interactive local differential privacy (LDP): learning and refutation. Learning requires finding a concept that best fits an unknown tar…
Near Neighbor Search via Efficient Average Distortion Embeddings
Deepanshu Kush, Aleksandar Nikolov, Haohua Tang
A recent series of papers by Andoni, Naor, Nikolov, Razenshteyn, and Waingarten (STOC 2018, FOCS 2018) has given approximate near neighbour search (NNS) data structures for a wide…
On the Computational Complexity of Linear Discrepancy
Lily Li, Aleksandar Nikolov
Many problems in computer science and applied mathematics require rounding a vector of fractional values lying in the interval to a binary vector …
Private Query Release Assisted by Public Data
Raef Bassily, Albert Cheu, Shay Moran +3
We study the problem of differentially private query release assisted by access to public data. In this problem, the goal is to answer a large class of statistical qu…
Maximizing Determinants under Matroid Constraints
Vivek Madan, Aleksandar Nikolov, Mohit Singh +1
Given vectors and a matroid , we study the problem of finding a basis of such that is maximized…
Locally Private Hypothesis Selection
Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni +3
We initiate the study of hypothesis selection under local differential privacy. Given samples from an unknown probability distribution and a set of probability distribution…