Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-014 | 26th February 2008 00:00

Separating NOF communication complexity classes RP and NP

RSS-Feed




TR08-014
Authors: Matei David
Publication: 28th February 2008 15:24
Downloads: 2953
Keywords: 


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



ISSN 1433-8092 | Imprint