Conference item
Further collapses in TFNP
- Abstract:
- We show EOPL = PLS ∩ PPAD. Here the class EOPL consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubáček and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse CLS = PLS ∩ PPAD by Fearnley et al. (STOC 2021). We also prove a companion result SOPL = PLS ∩ PPADS, where SOPL is the class associated with the Sink-of-Potential-Line problem.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Authors
Bibliographic Details
- Publisher:
- Schloss Dagstuhl Publisher's website
- Host title:
- 37th Computational Complexity Conference (CCC 2022)
- Series:
- Leibniz International Proceedings in Informatics
- Volume:
- 234
- Pages:
- 33:1--33:15
- Publication date:
- 2022-07-11
- Acceptance date:
- 2022-04-30
- Event title:
- 37th Computational Complexity Conference (CCC 2022)
- Event location:
- Philadelphia, PA, USA
- Event website:
- https://www.computationalcomplexity.org/
- Event start date:
- 2022-07-21
- Event end date:
- 2022-07-23
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 978-3-95977-241-9
Item Description
Terms of use
- Copyright holder:
- Göös et al.
- Copyright date:
- 2022
- Rights statement:
- © Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao; licensed under Creative Commons License CC-BY 4.0
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record