ECCC-Report TR13-005https://eccc.weizmann.ac.il/report/2013/005Comments and Revisions published for TR13-005en-usWed, 02 Jan 2013 22:45:59 +0200
Paper TR13-005
| Communication Lower Bounds Using Directional Derivatives |
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2013/005We prove that the set disjointness problem has randomized communication complexity
$\Omega(\sqrt{n}/2^{k}k)$ in the number-on-the-forehead model with $k$ parties, a quadratic improvement
on the previous bound $\Omega(\sqrt{n}/2^{k})^{1/2}$. Our result remains valid for quantum
protocols, where it is essentially tight. Proving it was an open problem since 1997,
even in restricted settings such as one-way classical protocols with $k=4$ parties. We
obtain other near-optimal results for multiparty set disjointness, including an XOR lemma,
a direct product theorem, and lower bounds for nondeterministic and Merlin-Arthur
protocols. The proof contributes a novel technique for lower bounds on multiparty
communication, based on directional derivatives of communication protocols over the reals.Wed, 02 Jan 2013 22:45:59 +0200https://eccc.weizmann.ac.il/report/2013/005