Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-124 | 3rd January 2024 10:16

Explicit separations between randomized and deterministic Number-on-Forehead communication

RSS-Feed




Revision #1
Authors: Zander Kelley, Shachar Lovett, Raghu Meka
Accepted on: 3rd January 2024 10:16
Downloads: 227
Keywords: 


Abstract:

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 \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.



Changes to previous version:

Small fixes


Paper:

TR23-124 | 24th August 2023 01:12

Explicit separations between randomized and deterministic Number-on-Forehead communication





TR23-124
Authors: Zander Kelley, Shachar Lovett, Raghu Meka
Publication: 24th August 2023 01:13
Downloads: 662
Keywords: 


Abstract:

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 \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.



ISSN 1433-8092 | Imprint