The complexity of continuous local search

Gordon, Spencer L

Permalink

https://hdl.handle.net/2142/97391 Copy

Description

Title

The complexity of continuous local search

Author(s)

Gordon, Spencer L

Issue Date

2017-04-21

Director of Research (if dissertation) or Advisor (if thesis)

Mehta, Ruta

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

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

Abstract

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.

Graduation Semester

2017-05

Type of Resource

text

Permalink

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

Copyright and License Information

Copyright 2017 Spencer Gordon

Owning Collections