97 citations · 255 across the 28 of their papers we have counts for
22 papers · 1 filter
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…
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 …
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…
The Power of Factorization Mechanisms in Local and Central Differential Privacy
Alexander Edmonds, Aleksandar Nikolov, Jonathan Ullman
We give new characterizations of the sample complexity of answering linear queries (statistical queries) in the local and central models of differential privacy: *In the non-intera…
Preconditioning for the Geometric Transportation Problem
Andrey Boris Khesin, Aleksandar Nikolov, Dmitry Paramonov
In the geometric transportation problem, we are given a collection of points in -dimensional Euclidean space, and each point is given a supply of units of mass, where…
On Mean Estimation for General Norms with Statistical Queries
Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn +1
We study the problem of mean estimation for high-dimensional distributions, assuming access to a statistical query oracle for the distribution. For a normed space $X = (\mathbb{R}^…
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh +3
Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rou…
Towards Instance-Optimal Private Query Release
Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov +1
We study efficient mechanisms for the query release problem in differential privacy: given a workload of statistical queries, output approximate answers to the queries while sa…
Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design
Aleksandar Nikolov, Mohit Singh, Uthaipon Tao Tantipongpipat
We study the optimal design problems where the goal is to choose a set of linear measurements to obtain the most accurate estimate of an unknown vector in dimensions. We study…
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
Daniel Dadush, Shashwat Garg, Shachar Lovett +1
An important theorem of Banaszczyk (Random Structures & Algorithms `98) states that for any sequence of vectors of norm at most and any convex body of Gaussian m…
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…
Approximate Near Neighbors for General Symmetric Norms
Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov +2
We show that every symmetric normed space admits an efficient nearest neighbor search data structure with doubly-logarithmic approximation. Specifically, for every , $d = n^{o(1…
An Improved Private Mechanism for Small Databases
Aleksandar Nikolov
We study the problem of answering a workload of linear queries , on a database of size at most drawn from a universe under the con…
Parallel Algorithms for Geometric Graph Problems
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak +1
We give algorithms for geometric graph problems in the modern parallel models inspired by MapReduce. For example, for the Minimum Spanning Tree (MST) problem over a set of points i…
Approximating Hereditary Discrepancy via Small Width Ellipsoids
Aleksandar Nikolov, Kunal Talwar
The Discrepancy of a hypergraph is the minimum attainable value, over two-colorings of its vertices, of the maximum absolute imbalance of any hyperedge. The Hereditary Discrepancy…
Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations
Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar
Consider a database of people, each represented by a bit-string of length corresponding to the setting of binary attributes. A -way marginal query is specified by a…
Nearly Optimal Private Convolution
Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov
We study computing the convolution of a private input with a public input , while satisfying the guarantees of -differential privacy. Convolution is a fundamental op…
The Geometry of Differential Privacy: the Sparse and Approximate Cases
Aleksandar Nikolov, Kunal Talwar, Li Zhang
In this work, we study trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables an…
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…
Private Decayed Sum Estimation under Continual Observation
Jean Bolot, Nadia Fawaz, S. Muthukrishnan +2
In monitoring applications, recent data is more important than distant data. How does this affect privacy of data analysis? We study a general class of data analyses - computing pr…