Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > WILLIAM PIRES:
All reports by Author William Pires:

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