[Facets-of-complexity] Invitation and link to Monday Lectures - January 25th 2021 - online via zoom

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

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.
All Monday Lectures and Colloquia of winter term 2020/21 will be given online via zoom.

You may find valid Invitation for zoom throughout all winter term here:
http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on January 25th 2021 at 14:15 h & 15:00 !

Online via:
Zoom - Invitation

Time: Monday, January 25th - 14:15 h

Lecture: Michaela Borzechowski

Title: One-Permutation-Discrete-Contraction is UEOPL-hard

Abstract:

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.

Time: Monday, January 25th - 15:00 h

Lecture: Shubhang Mittal

Title: tba

Abstract:

tba