Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur 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.
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
Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen, Ashkan Norouzi Fard