End of Potential Line

25^th April 2018, 13:00
John Fearnley
University of Liverpool

Abstract

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 that admit a single combinatorial proof of their joint membership in the complexity classes PPAD of fixpoint problems and PLS of local search problems. Our two main results are two show that both PL-Contraction (Piecewise-Linear Contraction, defined with a linear FIXP circuit) and P-LCP are in EOPL. Our reductions imply that the promise versions of PL-Contraction and P-LCP are in the promise class UniqueEOPL, which corresponds to the case of a single potential line. This also shows that simple-stochastic, discounted, mean-payoff, and parity games are in EOPL.

Joint work with: Spencer Gordon, Ruta Mehta, and Rahul Savani.