Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LAS VEGAS:
Reports tagged with Las Vegas:
TR97-029 | 20th August 1997
Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger

On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations

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


TR21-123 | 25th August 2021
Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani

On public-coin zero-error randomized communication complexity

Revisions: 1

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

more >>>



ISSN 1433-8092 | Imprint