Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.
DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.
We show EOPL = PLS \cap PsansP \sansP AD. 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'acv \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 \cap PsansP \sansP AD by Fearnley et al. (STOC 2021). We also prove a companion result SOPL = PLS \cap PsansP \sansP ADS, where SOPL is the class associated with the SINK -OF -POTENTIAL -LINE problem.
Mika Tapani Göös, Gilbert Théodore Maystre, Alexandros Paul Hollender
Ola Nils Anders Svensson, Moran Feldman, Ashkan Norouzi Fard