2 citations · 2 across the 1 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2022★ 2 cited
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…
cs.CC2022
Further Collapses in TFNP
Mika Göös, Alexandros Hollender, Siddhartha Jain +4
We show . Here the class consists of all total search problems that reduce to the End-of-Potential-Line problem, which…