97 citations · 255 across the 28 of their papers we have counts for
36 papers
Discrepancy Theory: An Algorithmic and Geometric Perspective
Nikhil Bansal, Aleksandar Nikolov
Combinatorial discrepancy theory is a subject with roots in combinatorics, geometry, and number theory, and with numerous applications to mathematics and computer science. At its c…
On the Gap between Hereditary Discrepancy and the Determinant Lower Bound
Lily Li, Aleksandar Nikolov
The determinant lower bound of Lovasz, Spencer, and Vesztergombi [European Journal of Combinatorics, 1986] is a powerful general way to prove lower bounds on the hereditary discrep…
General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation
Aleksandar Nikolov, Haohua Tang
We investigate unbiased high-dimensional mean estimators in differential privacy. We consider differentially private mechanisms whose expected output equals the mean of the input d…
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…
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 …
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…
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…
Tusnády's problem, the transference principle, and non-uniform QMC sampling
Christoph Aistleitner, Dmitriy Bilyk, Aleksandar Nikolov
It is well-known that for every and there exist point sets whose discrepancy with respect to the Lebesgue measure is of order at…
Tighter Bounds for the Discrepancy of Boxes and Polytopes
Aleksandar Nikolov
Combinatorial discrepancy is a complexity measure of a collection of sets which quantifies how well the sets in the collection can be simultaneously balanced. More precisely, we ar…
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…
Randomized Rounding for the Largest Simplex Problem
Aleksandar Nikolov
The maximum volume -simplex problem asks to compute the -dimensional simplex of maximum volume inside the convex hull of a given set of points in . We give…
Factorization Norms and Hereditary Discrepancy
Jiri Matousek, Aleksandar Nikolov, Kunal Talwar
The norm of a real matrix is the minimum number such that the column vectors of are contained in a -centered ellipsoid whi…