5 citations · 13 across the 19 of their papers we have counts for
5 papers · 1 filter
Tight Inapproximability for Graphical Games
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
We provide a complete characterization for the computational complexity of finding approximate equilibria in two-action graphical games. We consider the two most well-studied appro…
Pure-Circuit: Tight Inapproximability for PPAD
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
The current state-of-the-art methods for showing inapproximability in PPAD arise from the -Generalized-Circuit (-GCircuit) problem. Rubinstein (2018) show…
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…
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…
Constant Inapproximability for PPA
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
In the -Consensus-Halving problem, we are given probability measures on the interval , and the goal is to partition into two parts…