Separating NOF communication complexity classes RP and NP

Simple item page
dc.creatorDavid, Matei
dc.creatorPitassi, Toniann
dc.date2008-02-26
dc.date.accessioned2026-07-07T09:23:21Z
dc.date.available2026-07-07T09:23:21Z
dc.descriptionWe 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)).
dc.identifierhttps://arxiv.org/abs/0802.3860
dc.identifierhttp://arxiv.org/abs/0802.3860
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/155703
dc.subjectComputational Complexity
dc.subjectF.1.3
dc.titleSeparating NOF communication complexity classes RP and NP
dc.typetext

Files

Collections

arXiv