You are cordially invited to our next Monday Lecture. Next Monday
Lecture, there will be again the hearing of our
next PhD candidates. We will have two talks this time. Talks will be 30 min. 15
min discussions, 15 min break. You may find valid Invitation for zoom throughout all winter term
here: Invitation link: Monday Lecture will be on January 25th 2021 at 14:15
h & 15:00 ! Zoom - Invitation Time: Monday, January 25th - 14:15 h Lecture: Michaela Borzechowski Title: One-Permutation-Discrete-Contraction is UEOPL-hard Abstract: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. Time: Monday, January 25th - 15:00 h Lecture: Shubhang Mittal Title: tba Abstract: |