BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T003246Z
UID:Seminar-EcCo-573@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20180425T130000
DTEND:20180425T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:John Fearnley: End of Potential Line\n\nWe 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.\n\nJoint work with: Spencer Gordon, Ruta Mehta, and Rahul Savani.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=573
LOCATION:
END:VEVENT
END:VCALENDAR