Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication

We study the power of randomness in the Number-on-Forehead (NOF) model in communication complexity. We construct an explicit 3-player function f :[ N ] 3 → {0,1}, such that: (i) there exist a randomized NOF protocol computing it that sends a constant number of bits; but (ii) any deterministic or nondeterministic NOF protocol computing it requires sending about (log N ) 1/3 many bits. This exponentially improves upon the previously best-known such separation. At the core of our proof is an extension of a recent result on sets of integers without 3-term arithmetic progressions into a non-arithmetic setting.

Authors

• Zander Kelley
• Shachar Lovett
• Raghu Meka

Keywords

• Cylinder Intersections
• Grid Norms
• Multiparty NOF