{"id":"arxiv/2603.19490","url":"https://arxiv.org/abs/2603.19490","tags":["cs.CC","math.CO"],"score":0,"title":"Communication Complexity of Disjointness under Product Distributions","domain":"cs.CC","source":"arxiv","authors":["Zach Hunter","Aleksa Milojević","Benny Sudakov","Istvan Tomon"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-19","reactions":{}}