The complexity class Unique End of Potential Line (UEOPL) was introduced in 2018 by Fearnley et al. and contains many interesting search problems.
UEOPL captures problems that have either by definition a unique solution, like the Arrival problem, or that are promised to have a unique solution by some property, like the P-Matrix linear complementary problem.
Furthermore the problems in UEOPL have the property that the candidate solutions can be interpreted as an exponentially large graph which form a line, i.e. each node has in and out degree at most 1. The solution of each problem is at the end of that line.
In 2017, Daskalakis, Tzamos and Zampetakis proved the problem of finding a fixpoint of a contraction map in a continuous space whose existence is guaranteed by the Banach fixed point theorem to be CLS-complete.
A discrete version of the contraction problem, called One-Permutation-Discrete-Contraction, is proven to be the first UEOPL-complete problem.
This proof is particularly interesting because it is currently the only one of its kind and lays the groundwork for future UEOPL-completeness proofs.
This talk will provide an overview of the reduction from the problem Unique-End-of-Potential-Line to One-Permutation-Discrete-Contraction as well as correcting some errors that were done in the original paper.