Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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.
Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen, Ashkan Norouzi Fard
Mika Tapani Göös, Gilbert Théodore Maystre, Alexandros Paul Hollender, Siddhartha Jain, Ran Tao
Volkan Cevher, Ilija Bogunovic, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakub Tarnawski