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 #2 to TR21-123 | 21st March 2022 19:23

On public-coin zero-error randomized communication complexity

RSS-Feed




Revision #2
Authors: Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani
Accepted on: 21st March 2022 19:23
Downloads: 278
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.



Changes to previous version:

We fix an error in the proof of the main theorem in the previous version of this article.


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

On public-coin zero-error randomized communication complexity





Revision #1
Authors: Ben Davis, Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Hamza Usmani
Accepted on: 6th September 2021 17:37
Downloads: 518
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: 803
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