Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
Aleksandar Nikolov, Haohua Tang, Jonathan Ullman
In this paper we consider several related online computation problems. First, we study answering sequences of statistical queries arriving online, and being answered immediately wh…
cs.DS2025
Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries
Christian Janos Lebeda, Aleksandar Nikolov, Haohua Tang
We revisit the task of releasing marginal queries under differential privacy with additive (correlated) Gaussian noise. We first give a construction for answering arbitrary workloa…
cs.DS2021
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…