Name
Abstract | ||
|---|---|---|
We prove a direct sum theorem for randomized communication complexity. Ignoring loga- rithmic factors, our results show that: • Computing n copies of a function requires p n times the communication. • For average case complexity, given any distribution µ on inputs, computing n copies of the function on n independent inputs sampled according to µ requires p n times the commu- nication for computing one copy. • If µ is a product distribution, computing n copies on n independent inputs sampled ac- cording to µ requires n times the communication. We also study the complexity of computing the parity of n evaluations of f, and obtain results analogous to those above. Our results are obtained by designing new compression schemes that can compress the com- munication in interactive processes that do not reveal too much information about their inputs. This generalizes the notion of traditional compression, which can be viewed as compressing protocols that involve only one way communication. |
Year | Venue | Keywords |
|---|---|---|
2009 | Electronic Colloquium on Computational Complexity (ECCC) | functional requirement,product distribution,communication complexity |
Field | DocType | Volume |
Discrete mathematics,Average-case complexity,Combinatorics,Direct sum,Communication complexity,Logarithm,Parity (mathematics),Mathematics,Fold (higher-order function) | Journal | 16 |
Citations | PageRank | References |
3 | 0.39 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boaz Barak | 1 | 2563 | 127.61 |
| Mark Braverman | 2 | 810 | 61.60 |
| xi guang chen | 3 | 3 | 0.39 |
| Anup Rao | 4 | 581 | 32.80 |