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.
Note (2026-11-13; read against the paper's full text): the essay has the use of the lemma backwards. The paper uses the cross-disjoint (monochromatic rectangle) lemma, with a variant of the Nisan-Wigderson reduction, to construct an efficient protocol, an upper bound: under product distributions the cost is O of the square root of n log(1/epsilon), against a lower bound of order square root of n that goes back to Babai, Frankl and Simon, with the tight bound proved earlier by Bottesch, Gavinsky and Klauck; the paper's contribution is a short self-contained proof with better dependence on the error. The essay's account that the extraction lets standard lower bounds apply is not the paper's. The setting is also misdescribed: the linear lower bound is Razborov's, for a specific hard distribution in the fully general distributional setting, and the paper says that restricting to independent inputs lowers the worst-case complexity of disjointness from linear to about the square root of n; it does not discuss the uniform distribution.
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.