97 citations · 255 across the 28 of their papers we have counts for
5 papers · 1 filter
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…
On The Hereditary Discrepancy of Homogeneous Arithmetic Progressions
Aleksandar Nikolov, Kunal Talwar
We show that the hereditary discrepancy of homogeneous arithmetic progressions is lower bounded by . This bound is tight up to the constant in the exponent. O…
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 Komlos Conjecture Holds for Vector Colorings
Aleksandar Nikolov
The Komlos conjecture in discrepancy theory states that for some constant K and for any m by n matrix A whose columns lie in the unit ball there exists a +/- 1 vector x such that t…