26 citations · 63 across the 16 of their papers we have counts for
10 papers · 1 filter
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…
Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds
Amos Beimel, Haim Kaplan, Yishay Mansour +3
A dynamic algorithm against an adaptive adversary is required to be correct when the adversary chooses the next update after seeing the previous outputs of the algorithm. We obtain…
Separating Adaptive Streaming from Oblivious Streaming
Haim Kaplan, Yishay Mansour, Kobbi Nissim +1
We present a streaming problem for which every adversarially-robust streaming algorithm must use polynomial space, while there exists a classical (oblivious) streaming algorithm th…
Adversarially Robust Streaming Algorithms via Differential Privacy
Avinatan Hassidim, Haim Kaplan, Yishay Mansour +2
A streaming algorithm is said to be adversarially robust if its accuracy guarantees are maintained even when the data stream is chosen maliciously, by an adaptive adversary. We est…
How to Find a Point in the Convex Hull Privately
Haim Kaplan, Micha Sharir, Uri Stemmer
We study the question of how to compute a point in the convex hull of an input set of points in in a differentially private manner. This question, which is…
The power of synergy in differential privacy: Combining a small curator with local randomizers
Amos Beimel, Aleksandra Korolova, Kobbi Nissim +2
Motivated by the desire to bridge the utility gap between local and trusted curator models of differential privacy for practical applications, we initiate the theoretical study of…