97 citations · 255 across the 28 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016
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…
cs.DS2016★ 2 cited
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…
cs.DS2016★ 1 cited
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…