The study of the computational power of randomized
computations is one of the central tasks of complexity theory. The
main goal of this paper is the comparison of the power of Las Vegas
computation and deterministic respectively nondeterministic
computation. We investigate the power of Las Vegas computation for ... more >>>

We prove that for every Boolean function, the public-coin zero-error randomized communication complexity and the deterministic communication complexity are polynomially equivalent.

more >>>