TFNP characterizations of proof systems and monotone circuits
Connections between proof complexity and circuit complexity have become major tools for obtaining lower bounds in both areas. These connections – which take the form of interpolation theorems and query-to-communication lifting theorems – translate efficient proofs into small circuits, and vice versa, allowing tools from one area to be applied to the other. Recently, the theory of TFNP has emerged
