Communication Complexity of Disjointness under Product Distributions

Read full text Summarise with VIRAT
Authors: Zach Hunter, Aleksa Milojević, Benny Sudakov, István Tomon
Cited by: 0
References: 12

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Determining the randomized (or distributional) communication complexity of disjointness is a central problem in communication complexity, having roots in the foundational work of Babai, Frankl, and Simon in the 1980s and culminating in the famous works of Kalyanasundaram-Schnitger and Razborov in 1992. However, the question of obtaining tight bounds for product distributions persisted until the more recent work of Bottesch, Gavinsky, and Klauck resolved it. In this note we revisit this classical problem and give a short, streamlined proof of the best bounds, with improved quantitative dependence on the error parameter. Our approach is based on a simple combinatorial lemma that may be of independent interest: if two sets drawn independently from two distributions are disjoint with non-negligible probability, then one can extract two subfamilies of reasonably large measure that are fully cross-disjoint (equivalently, a large monochromatic rectangle for disjointness).

Fields of Study & Subjects

Complexity and Algorithms in Graphs Computability Logic AI Algorithms Algorithms and Data Compression

Publication details

Journal / source
arXiv (Cornell University)
Publication date
19 March 2026
Language
EN
Document type
Preprint