8 papers
Stochastic Matching via Local Sparsification
Sara Ahmadian, Edith Cohen, Mohammad Roghani
The classic online stochastic matching problem typically requires immediate and irrevocable matching decisions. However, in many modern decentralized systems such as real-time ride…
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…
Hot PATE: Private Aggregation of Distributions for Diverse Task
Edith Cohen, Benjamin Cohen-Wang, Xin Lyu +3
The Private Aggregation of Teacher Ensembles (PATE) framework enables privacy-preserving machine learning by aggregating responses from disjoint subsets of sensitive data. Adaptati…
The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for Norm Estimation
Sara Ahmadian, Edith Cohen, Uri Stemmer
Dimensionality reduction via linear sketching is a powerful and widely used technique, but it is known to be vulnerable to adversarial inputs. We study the black-box adversarial se…
A Simple and Robust Protocol for Distributed Counting
Edith Cohen, Moshe Shechner, Uri Stemmer
We revisit the distributed counting problem, where a server must continuously approximate the total number of events occurring across sites while minimizing communication. The…