Separations in Proof Complexity and TFNP

Mika Göös, Alexandros Hollender, Siddhartha Jain +4

It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, however, that any such simulation needs to exploit huge coefficients: Re…