Given a propositional proof system $P$, we may define a formula $\text{Prf}^P_s(F)$ which is satisfiable if and only if the formula $F$ has a length $\leq s$ refutation in $P$. These formulas have received much attention in recent years due to their fundamental nature --- if a powerful proof ... more >>>

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

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

more >>>