Name
Title | ||
|---|---|---|
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness |
Abstract | ||
|---|---|---|
We prove that two-party randomized communication complexity satisfies a strong direct product property, so long as the communication lower bound is proved by a "corruption" or "one-sided discrepancy" method over a rectangular distribution. We use this to prove new n 驴(1) lower bounds for 3-player number-on-the-forehead protocols in which the first player speaks once and then the other two players proceed arbitrarily. Using other techniques, we also establish an 驴(n 1/(k驴1)/(k 驴 1)) lower bound for k-player randomized number-on-the-forehead protocols for the disjointness function in which all messages are broadcast simultaneously. A simple corollary of this is that general randomized number-on-the-forehead protocols require 驴(log n/(k 驴 1)) bits of communication to compute the disjointness function. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/s00037-007-0220-2 | Computational Complexity |
Keywords | Field | DocType |
direct sum,communication complexity,satisfiability,direct product,lower bound | Discrete mathematics,Broadcasting,Binary logarithm,Combinatorics,Direct product,Upper and lower bounds,Direct sum,Uniform distribution (continuous),Communication complexity,Corollary,Mathematics | Journal |
Volume | Issue | ISSN |
15 | 4 | 1016-3328 |
Citations | PageRank | References |
20 | 1.03 | 30 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Beame | 1 | 2234 | 176.07 |
| Toniann Pitassi | 2 | 2282 | 155.18 |
| Nathan Segerlind | 3 | 223 | 11.22 |
| Avi Wigderson | 4 | 8205 | 1064.31 |