Name
Abstract | ||
|---|---|---|
We provide a non-explicit separation of the number-on-forehead communication complexity classes RP and NP when the number of players is up to \delta log(n) for any \delta<1. Recent lower bounds on Set-Disjointness [LS08,CA08] provide an explicit separation between these classes when the number of players is only up to o(loglog(n)). |
Year | Venue | Keywords |
|---|---|---|
2008 | Electronic Colloquium on Computational Complexity | lower bound,computational complexity,communication complexity |
DocType | Volume | Citations |
Journal | abs/0802.3860 | 2 |
PageRank | References | Authors |
0.38 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matei David | 1 | 55 | 5.11 |
| Toniann Pitassi | 2 | 2282 | 155.18 |