28 citations · 174 across the 52 of their papers we have counts for
23 papers · 1 filter
Tight Bounds on the Cost of Adaptivity for the Meyerson Sketch
Edith Cohen, Elena Gribelyuk, Pasin Manurangsi +1
In online facility location, points arrive one at a time, and the algorithm must either open a facility at the arriving point or route the point to an existing facility. The Meyers…
Load Balancing under Adaptive Bin Deletions
Haim Kaplan, Shay Sapir, Uri Stemmer
We analyze a balls-and-bins game against an adaptive adversary that sequentially deletes bins. Starting with balls distributed across bins, the adversary deletes a bin in e…
Adaptively Robust Resettable Streaming
Edith Cohen, Elena Gribelyuk, Jelani Nelson +1
We study algorithms in the resettable streaming model, where the value of each key can either be increased or reset to zero. The model is suitable for applications such as active r…
Tight Bounds for Answering Adaptively Chosen Concentrated Queries
Emma Rapoport, Edith Cohen, Uri Stemmer
Most work on adaptive data analysis assumes that samples in the dataset are independent. When correlations are allowed, even the non-adaptive setting can become intractable, unless…
Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
Edith Cohen, Mihir Singhal, Uri Stemmer
Cardinality sketches are compact data structures that efficiently estimate the number of distinct elements across multiple queries while minimizing storage, communication, and comp…
On Differentially Private Linear Algebra
Haim Kaplan, Yishay Mansour, Shay Moran +2
We introduce efficient differentially private (DP) algorithms for several linear algebraic tasks, including solving linear equalities over arbitrary fields, linear inequalities ove…
One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
Edith Cohen, Jelani Nelson, Tamás Sarlós +2
Cardinality sketches are compact data structures for representing sets or vectors. These sketches are space-efficient, typically requiring only logarithmic storage in the input siz…
Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Model
Menachem Sadigurschi, Moshe Shechner, Uri Stemmer
Streaming algorithms are typically analyzed in the oblivious setting, where we assume that the input stream is fixed in advance. Recently, there is a growing interest in designing…
Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs
Edith Cohen, Jelani Nelson, Tamás Sarlós +1
CountSketch and Feature Hashing (the "hashing trick") are popular randomized dimensionality reduction methods that support recovery of -heavy hitters (keys where $v_i^2…
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…
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…
A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
Idan Attias, Edith Cohen, Moshe Shechner +1
Classical streaming algorithms operate under the (not always reasonable) assumption that the input stream is fixed in advance. Recently, there is a growing interest in designing ro…
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…
Privately Learning Thresholds: Closing the Exponential Gap
Haim Kaplan, Katrina Ligett, Yishay Mansour +2
We study the sample complexity of learning threshold functions under the constraint of differential privacy. It is assumed that each labeled example in the training data is the inf…
Differentially Private k-Means with Constant Multiplicative Error
Haim Kaplan, Uri Stemmer
We design new differentially private algorithms for the Euclidean k-means problem, both in the centralized model and in the local model of differential privacy. In both models, our…
Heavy Hitters and the Structure of Local Privacy
Mark Bun, Jelani Nelson, Uri Stemmer
We present a new locally differentially private algorithm for the heavy hitters problem which achieves optimal worst-case error as a function of all standardly considered parameter…
Clustering Algorithms for the Centralized and Local Models
Kobbi Nissim, Uri Stemmer
We revisit the problem of finding a minimum enclosing ball with differential privacy: Given a set of points in the Euclidean space and an integer , the…
Locating a Small Cluster Privately
Kobbi Nissim, Uri Stemmer, Salil Vadhan
We present a new algorithm for locating a small cluster of points with differential privacy [Dwork, McSherry, Nissim, and Smith, 2006]. Our algorithm has implications to private da…
Simultaneous Private Learning of Multiple Concepts
Mark Bun, Kobbi Nissim, Uri Stemmer
We investigate the direct-sum problem in the context of differentially private PAC learning: What is the sample complexity of solving learning tasks simultaneously under differ…