5 citations · 11 across the 8 of their papers we have counts for
12 papers
On Pigeonhole Principles and Ramsey in TFNP
Siddhartha Jain, Jiawei Li, Robert Robere +1
We show that the TFNP problem RAMSEY is not black-box reducible to PIGEON, refuting a conjecture of Goldberg and Papadimitriou in the black-box setting. We prove this by giving red…
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…
Proofs, Circuits, and Communication
Susanna F. de Rezende, Mika Göös, Robert Robere
We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and que…
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…
On the Power and Limitations of Branch and Cut
Noah Fleming, Mika Göös, Russell Impagliazzo +4
The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simul…
KRW Composition Theorems via Lifting
Susanna F. de Rezende, Or Meir, Jakob Nordström +2
One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., ). Karchmer, Raz…