Files in this item
Files  Description  Format 

application/pdf GORDONTHESIS2017.pdf (2MB)  (no description provided) 
Description
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 UrbanaChampaign 
Degree:  M.S. 
Genre:  Thesis 
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 wellknown 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 PLCP, i.e., the problem of solving a Pmatrix 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 twoway 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 PLCP to ENDOFPOTENTIALLINE, thus making ENDOFPOTENTIALLINE and ENDOFMETEREDLINE at least as likely to be hard for CLS as PLCP. This result leverages the monotonic structure of Lemke paths for PLCP problems, making ENDOFPOTENTIALLINE a likely candidate to capture the exact complexity of PLCP; we note that the structure of LemkeHowson paths for finding a Nash equilibrium in a twoplayer game directly motivated the definition of the complexity class PPAD, which ended up capturing this problem’s complexity exactly. Finally, we reduce the 2dimensional version of CONTRACTION to ENDOFPOTENTIALLINE, providing further evidence that ENDOFPOTENTIALLINE is CLShard. 
Issue Date:  20170421 
Type:  Text 
URI:  http://hdl.handle.net/2142/97391 
Rights Information:  Copyright 2017 Spencer Gordon 
Date Available in IDEALS:  20170810 
Date Deposited:  201705 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois