Disjointness is the canonical hard problem in communication complexity. Alice holds a set, Bob holds a set, and they want to determine whether the sets share any element. The randomized communication complexity of disjointness under the uniform distribution is well understood and requires linear communication. Under product distributions — where Alice's and Bob's sets are sampled independently — the question is subtler.
Hunter, Milojević, Sudakov, and Tomon provide a short, streamlined proof of the best known bounds with improved dependence on the error parameter. The combinatorial core is a structural lemma: when two independently sampled set families are disjoint with meaningful probability, one can extract two subfamilies of reasonably large measure that are fully cross-disjoint — every set in one subfamily is disjoint from every set in the other.
This extraction is the key step. It converts a probabilistic condition (the families are likely disjoint) into a deterministic structure (there exist large subfamilies that are always disjoint). Once the cross-disjoint core is identified, standard communication complexity lower bounds apply because any protocol must distinguish between the cross-disjoint subfamilies and the rest of the distribution.
The through-claim is about the relationship between probabilistic and deterministic structure. The probabilistic statement — “these families are usually disjoint” — seems weaker than the deterministic statement — “these subfamilies are always disjoint.” But the extraction lemma shows they are connected: enough probabilistic disjointness implies the existence of a deterministic core. The hard instances are not scattered randomly through the distribution. They concentrate into a structured subset that a simpler proof can target directly.