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)).
arXiv: Computer Science::Computer Science and Game Theory Computer Science::Computational Complexity
FOS: Computer and information sciences, Computational Complexity (cs.CC), F.1.3
FOS: Computer and information sciences, Computational Complexity (cs.CC), F.1.3
arXiv: Computer Science::Computer Science and Game Theory Computer Science::Computational Complexity
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)).