1 citations · 1 across the 10 of their papers we have counts for
4 papers · 1 filter
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…
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…
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…