Explicit separations between randomized and deterministic Number-on-Forehead communication
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909059949527040 |
|---|---|
| author | Kelley, Zander Lovett, Shachar Meka, Raghu |
| author_facet | Kelley, Zander Lovett, Shachar Meka, Raghu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_12451 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Explicit separations between randomized and deterministic Number-on-Forehead communication Kelley, Zander Lovett, Shachar Meka, Raghu Computational Complexity Combinatorics 68Q11, 68Q17 F.2.2; F.1.3 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. |
| title | Explicit separations between randomized and deterministic Number-on-Forehead communication |
| topic | Computational Complexity Combinatorics 68Q11, 68Q17 F.2.2; F.1.3 |
| url | https://arxiv.org/abs/2308.12451 |