Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > APPROXIMATION DEGREE:
Reports tagged with Approximation degree:
TR08-002 | 19th December 2007

#### Multiparty Communication Complexity of Disjointness

Revisions: 3

We extend the 'Generalized Discrepancy' technique suggested by Sherstov to the `Number on the Forehead' model of multiparty communication. This allows us to prove strong lower bounds of n^{\Omega(1)} on the communication needed by k players to compute the Disjointness function, provided $k$ is a constant. In general, our method ... more >>>

TR08-014 | 26th February 2008
Matei David

#### Separating NOF communication complexity classes RP and NP

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)).

... more >>>

ISSN 1433-8092 | Imprint