Fearnley, John, Gordon, Spencer, Mehta, Ruta and Savani, Rahul 
ORCID: 0000-0003-1262-7831
(2018)
End of Potential Line.
.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
1804.03450v2.pdf - Submitted version Download (647kB) |
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. EOPL is a combinatorially-defined alternative to the class CLS (for Continuous Local Search), which was introduced in with the goal of capturing the complexity of some well-known problems in PPAD $\cap$ PLS that have resisted, in some cases for decades, attempts to put them in polynomial time. Two of these are Contraction, the problem of finding a fixpoint of a contraction map, and P-LCP, the problem of solving a P-matrix Linear Complementarity Problem. We show that EndOfPotentialLine is in CLS via a two-way reduction to EndOfMeteredLine. The latter was defined in to show query and cryptographic lower bounds for CLS. Our two main results are to show that both PL-Contraction (Piecewise-Linear Contraction) 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. Using the insights from our reduction for PL-Contraction, we obtain the first polynomial-time algorithms for finding fixed points of contraction maps in fixed dimension for any $\ell_p$ norm, where previously such algorithms were only known for the $\ell_2$ and $\ell_\infty$ norms. Our reduction from P-LCP to EndOfPotentialLine allows a technique of Aldous to be applied, which in turn gives the fastest-known randomized algorithm for the P-LCP.
| Item Type: | Other |
|---|---|
| Additional Information: | v2 includes runtimes for P-LCP algorithms based on USOs in related work |
| Uncontrolled Keywords: | cs.CC, cs.CC, cs.GT |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 02 May 2018 08:13 |
| Last Modified: | 19 Jan 2023 06:34 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3020819 |
Share
Share
