Separating NOF communication complexity classes RP and NP
classification
💻 cs.CC
keywords
classescommunicationcomplexitydeltanumberplayersseparationwhen
read the original 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)).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.