All reports by Author Ben Davis:

__
TR23-068
| 10th May 2023
__

Ben Davis, Robert Robere#### Colourful TFNP and Propositional Proofs

Revisions: 1

__
TR21-123
| 25th August 2021
__

Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani#### On public-coin zero-error randomized communication complexity

Revisions: 2

Ben Davis, Robert Robere

Recent work has shown that many of the standard TFNP classes — such as PLS, PPADS, PPAD, SOPL, and EOPL — have corresponding proof systems in propositional proof complexity, in the sense that a total search problem is in the class if and only if the totality of the problem ... more >>>

Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani

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

more >>>