Files in this item



application/pdfGORDON-THESIS-2017.pdf (2MB)
(no description provided)PDF


Title:The complexity of continuous local search
Author(s):Gordon, Spencer L
Advisor(s):Mehta, Ruta
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(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, METAMETRICCONTRAC- TION, 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 ENDOFPOTEN- TIALLINE 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 ENDOFPO- TENTIALLINE 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 ENDOFPO- TENTIALLINE, providing further evidence that ENDOFPOTENTIALLINE is CLS- hard.
Issue Date:2017-04-21
Rights Information:Copyright 2017 Spencer Gordon
Date Available in IDEALS:2017-08-10
Date Deposited:2017-05

This item appears in the following Collection(s)

Item Statistics