28 citations · 244 across the 83 of their papers we have counts for
5 papers · 2 filters
A Note on Sanitizing Streams with Differential Privacy
Haim Kaplan, Uri Stemmer
The literature on data sanitization aims to design algorithms that take an input dataset and produce a privacy-preserving version of it, that captures some of its statistical prope…
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…
Online Weighted Matching with a Sample
Haim Kaplan, David Naori, Danny Raz
We study the greedy-based online algorithm for edge-weighted matching with (one-sided) vertex arrivals in bipartite graphs, and edge arrivals in general graphs. This algorithm was…
Locality Sensitive Hashing for Efficient Similar Polygon Retrieval
Haim Kaplan, Jay Tenenbaum
Locality Sensitive Hashing (LSH) is an effective method of indexing a set of items to support efficient nearest neighbors queries in high-dimensional spaces. The basic idea of LSH…
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…