Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with class separation:
TR08-014 | 26th February 2008
Matei David

Separating NOF communication complexity classes RP and NP

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

... more >>>

TR20-059 | 16th April 2020
Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma

Pr-ZSUBEXP is not contained in Pr-RP

Revisions: 1

We unconditionally prove there exists a promise problem in promise ZSUBEXP that cannot be solved in promise RP.
The proof technique builds upon Kabanets' easy witness method [Kab01] as implemented by Impagliazzo et. al [IKW02], with a separate diagonalization carried out on each of the two alternatives in the ... more >>>

ISSN 1433-8092 | Imprint