11 citations · 22 across the 9 of their papers we have counts for
4 papers · 1 filter
Unique End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta +1
This paper studies the complexity of problems in PPAD PLS that have unique solutions. Three well-known examples of such problems are the problem of finding a fixpoint of a c…
Smoothed Efficient Algorithms and Reductions for Network Coordination Games
Shant Boodaghians, Rucha Kulkarni, Ruta Mehta
Worst-case hardness results for most equilibrium computation problems have raised the need for beyond-worst-case analysis. To this end, we study the smoothed complexity of finding…
Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium
Pravesh K. Kothari, Ruta Mehta
Several works have shown unconditional hardness (via integrality gaps) of computing equilibria using strong hierarchies of convex relaxations. Such results however only apply to th…
End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta +1
We introduce the problem EndOfPotentialLine and the corresponding complexity class EOPL of all problems that can be reduced to it in polynomial time. This class captures problems t…