Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR21-123 | 6th September 2021 17:37

On public-coin zero-error randomized communication complexity

RSS-Feed




Revision #1
Authors: Ben Davis, Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Hamza Usmani
Accepted on: 6th September 2021 17:37
Downloads: 47
Keywords: 


Abstract:

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


Paper:

TR21-123 | 25th August 2021 00:06

On public-coin zero-error randomized communication complexity





TR21-123
Authors: Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani
Publication: 25th August 2021 01:39
Downloads: 334
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint