{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/97391"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/97391","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"The complexity of continuous local search","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Gordon, Spencer L"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Mehta, Ruta"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-08-10T19:15:22Z","date_published":"2017-08-10T19:15:22Z","updated_at":"2026-07-22T22:24:34Z","subjects":["Theoretical computer science","Algorithmic game theory","Computational complexity","Linear complementarity problem","Contraction map"],"languages":["en"],"rights":["Copyright 2017 Spencer Gordon"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/97391","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Mehta, Ruta"]},{"key":"dc:creator","label":"Author","values":["Gordon, Spencer L"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-08-10T19:15:22Z","2017-04-21","2017-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Theoretical computer science","Algorithmic game theory","Computational complexity","Linear complementarity problem","Contraction map"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Spencer Gordon"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/97391"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Spencer Gordon, accepted the attached license on 2017-04-18 at 10:36.","The student, Spencer Gordon, submitted this Thesis for approval on 2017-04-18 at 10:42.","This Thesis was approved for publication on 2017-04-21 at 13:26.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10848 on 2017-08-10 at 13:42:04","Made available in DSpace on 2017-08-10T19:15:22Z (GMT). No. of bitstreams: 2 GORDON-THESIS-2017.pdf: 1649950 bytes, checksum: b2aaf6c871d2798b66a35a16014b34ae (MD5) LICENSE.txt: 4211 bytes, checksum: c89ffff8b0ea5714f835bace2a495f86 (MD5) Previous issue date: 2017-04-21"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["The complexity of continuous local search"]}]}],"canonical_facts":{"dc:contributor":["Mehta, Ruta"],"dc:creator":["Gordon, Spencer L"],"dc:date":["2017-08-10T19:15:22Z","2017-04-21","2017-05"],"dc:description":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Spencer Gordon, accepted the attached license on 2017-04-18 at 10:36.","The student, Spencer Gordon, submitted this Thesis for approval on 2017-04-18 at 10:42.","This Thesis was approved for publication on 2017-04-21 at 13:26.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10848 on 2017-08-10 at 13:42:04","Made available in DSpace on 2017-08-10T19:15:22Z (GMT). No. of bitstreams: 2 GORDON-THESIS-2017.pdf: 1649950 bytes, checksum: b2aaf6c871d2798b66a35a16014b34ae (MD5) LICENSE.txt: 4211 bytes, checksum: c89ffff8b0ea5714f835bace2a495f86 (MD5) Previous issue date: 2017-04-21"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/97391"],"dc:language":["en"],"dc:rights":["Copyright 2017 Spencer Gordon"],"dc:subject":["Theoretical computer science","Algorithmic game theory","Computational complexity","Linear complementarity problem","Contraction map"],"dc:title":["The complexity of continuous local search"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:34Z"}