65 citations · 262 across the 38 of their papers we have counts for
32 papers · 1 filter
Sparse Dimensionality Reduction Revisited
Mikael Møller Høgsgaard, Lion Kamma, Kasper Green Larsen +2
The sparse Johnson-Lindenstrauss transform is one of the central techniques in dimensionality reduction. It supports embedding a set of points in into $m=O(\vare…
Private Counting of Distinct and k-Occurring Items in Time Windows
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +1
In this work, we study the task of estimating the numbers of distinct and -occurring items in a time window under the constraint of differential privacy (DP). We consider severa…
On the amortized complexity of approximate counting
Ishaq Aden-Ali, Yanjun Han, Jelani Nelson +1
Naively storing a counter up to value would require bits of memory. Nelson and Yu [NY22], following work of [Morris78], showed that if the query answers need only b…
Estimation of Entropy in Constant Space with Improved Sample Complexity
Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson +1
Recent work of Acharya et al. (NeurIPS 2019) showed how to estimate the entropy of a distribution over an alphabet of size up to additive error by streaming…
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +1
We study the problem of releasing the weights of all-pair shortest paths in a weighted undirected graph with differential privacy (DP). In this setting, the underlying graph is fix…
On the Robustness of CountSketch to Adaptive Inputs
Edith Cohen, Xin Lyu, Jelani Nelson +3
CountSketch is a popular dimensionality reduction technique that maps vectors to a lower dimension using randomized linear measurements. The sketch supports recovering -hea…