Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Further Collapses in TFNP
 
conference paper

Further Collapses in TFNP

Göös, Mika  
•
Hollender, Alexandros  
•
Jain, Siddhartha
Show more
2022
[Proceedings of CCC 2022]
37th Computational Complexity Conference (CCC)

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. LIPIcs, Vol. 234, 37th Computational Complexity Conference (CCC 2022), pages 33:1-33:15

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

LIPIcs-CCC-2022-33.pdf

Type

Publisher

Version

Published version

Access type

openaccess

License Condition

CC BY

Size

779.61 KB

Format

Adobe PDF

Checksum (MD5)

53412bb57cefb0d5143d9585a6813b5e

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés