The complexity of continuous local search

The complexity class CLS was introduced by Daskalakis and Papadimitriou in [9] with the goal of capturing the complexity of some well-known problems in PPAD ∩ PLS that have resisted, in some cases for decades, attempts to put them in polynomial time. No complete problem was known for CLS, and in [9], the problems CONTRACTION, i.e., the problem of finding an approximate fixpoint of a contraction map, and P-LCP, i.e., the problem of solving a P-matrix Linear Complementarity Problem, were identified as prime candidates. First, we present the first complete problem for CLS, METAMETRICCONTRACTION, which is closely related to the problem CONTRACTION. Second, we introduce ENDOFPOTENTIALLINE, which captures aspects of PPAD and PLS directly via a monotonic directed path, and show that ENDOFPOTENTIALLINE is in CLS via a two-way reduction to ENDOFMETEREDLINE. The latter was defined in [18] to keep track of how far a vertex is on the PPAD path via a restricted potential function, and was shown to be in CLS. Third, we reduce P-LCP to ENDOFPOTENTIALLINE, thus making ENDOFPOTENTIALLINE and ENDOFMETEREDLINE at least as likely to be hard for CLS as P-LCP. This result leverages the monotonic structure of Lemke paths for P-LCP problems, making ENDOFPOTENTIALLINE a likely candidate to capture the exact complexity of P-LCP; we note that the structure of Lemke-Howson paths for finding a Nash equilibrium in a two-player game directly motivated the definition of the complexity class PPAD, which ended up capturing this problem’s complexity exactly. Finally, we reduce the 2-dimensional version of CONTRACTION to ENDOFPOTENTIALLINE, providing further evidence that ENDOFPOTENTIALLINE is CLS-hard.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2017

Author dc:creator

• Gordon, Spencer L

Contributors dc:contributor

• Mehta, Ruta

• Theoretical computer science
• Algorithmic game theory
• Computational complexity
• Linear complementarity problem
• Contraction map

Statement dc:rights

• Copyright 2017 Spencer Gordon

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/97391

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/97391