ECCC-Report TR17-184https://eccc.weizmann.ac.il/report/2017/184Comments and Revisions published for TR17-184en-usWed, 29 Nov 2017 05:36:12 +0200
Paper TR17-184
| Inner Product and Set Disjointness: Beyond Logarithmically Many Parties |
Vladimir Podolskii,
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2017/184A basic goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems $f\colon(\{0,1\}^n)^{k}\to\{0,1\}$ with $k\gg\log n$ parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every $k\geq\log n$, showing in both cases that $\Theta(1+\lceil\log n\rceil/\log\lceil1+k/\log n\rceil)$ bits are necessary and sufficient. In particular, these problems admit constant-cost protocols if and only if the number of parties is $k\geq n^{\epsilon}$ for some constant $\epsilon>0.$Wed, 29 Nov 2017 05:36:12 +0200https://eccc.weizmann.ac.il/report/2017/184