Separating NOF communication complexity classes RP and NP

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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 δlog(n) for any δ<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)).

Keywords

Computational Complexity, F.1.3

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/155703

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0802.3860
 http://arxiv.org/abs/0802.3860

Collections

arXiv