# A Simple Proof of a New Set Disjointness with Applications to Data Streams

arXiv: https://arxiv.org/abs/2105.11338 · HTML: https://mlsanity.com/paper/2105.11338/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2021.

## Built on by (most cited first, 4 of 4)

- [On the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2202.13736/) (2022)
- [Streaming Algorithms for Learning with Experts: Deterministic Versus Robust](https://mlsanity.com/paper/2303.01709/) (2023)
- [Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2207.00956/) (2022)
- [Is Randomness Necessary for Adaptive Data Analysis?](https://mlsanity.com/paper/2607.07085/) (2026)

## Abstract (arXiv)

The multiplayer promise set disjointness is one of the most widely used problems from communication complexity in applications. In this problem there are k players with subsets S1, ldots, Sk, each drawn from 1, 2, ldots, n, and we are promised that either the sets are (1) pairwise disjoint, or (2) there is a unique element j occurring in all the sets, which are otherwise pairwise disjoint. The total communication of solving this problem with constant probability in the blackboard model is Omega(n/k). We observe for most applications, it instead suffices to look at what we call the ``mostly'' set disjointness problem, which changes case (2) to say there is a unique element j occurring in at least half of the sets, and the sets are otherwise disjoint. This change gives us a much simpler proof of an Omega(n/k) randomized total communication lower bound, avoiding Hellinger distance and Poincare inequalities. Using this we show several new results for data streams: beginitemize item for ℓ2-Heavy Hitters, any O(1)-pass streaming algorithm in the insertion-only model for detecting if an eps-ℓ2-heavy hitter exists requires min(frac1eps2log fraceps2nδ, frac1epsn1/2) bits of memory, which is optimal up to a log n factor. For deterministic algorithms and constant eps, this gives an Omega(n1/2) lower bound, improving the prior Omega(log n) lower bound. We also obtain lower bounds for Zipfian distributions. item for ℓp-Estimation, p > 2, we show an O(1)-pass Omega(n1-2/p log(1/δ)) bit lower bound for outputting an O(1)-approximation with probability 1-δ, in the insertion-only model. This is optimal, and the best previous lower bound was Omega(n1-2/p + log(1/δ)). enditemize