ECCC - TR21-123

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

Contact

Add Comment

Revision #2 Authors: Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani
Accepted on: 21st March 2022 19:23
Downloads: 522

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

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

Keywords:

Las Vegas, Zero-error

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