ECCC-Report TR23-124https://eccc.weizmann.ac.il/report/2023/124Comments and Revisions published for TR23-124en-usThu, 24 Aug 2023 01:13:54 +0300
Paper TR23-124
| Explicit separations between randomized and deterministic Number-on-Forehead communication |
Zander Kelley,
Shachar Lovett,
Raghu Meka
https://eccc.weizmann.ac.il/report/2023/124We 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 \to \{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 of the first and third authors on sets of integers without 3-term arithmetic progressions into a non-arithmetic setting.Thu, 24 Aug 2023 01:13:54 +0300https://eccc.weizmann.ac.il/report/2023/124