BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: 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 s
 olutions can be interpreted as an exponentially large graph which form a li
 ne\, i.e. each node has in and out degree at most 1. The solution of each p
 roblem is at the end of that line.  In 2017\, Daskalakis\, Tzamos and Zampe
 takis proved the problem of finding a fixpoint of a contraction map in a co
 ntinuous space whose existence is guaranteed by the Banach fixed point theo
 rem to be CLS-complete.  A discrete version of the contraction problem\, ca
 lled One-Permutation-Discrete-Contraction\, is proven to be the first UEOPL
 -complete problem.  This proof is particularly interesting because it is cu
 rrently the only one of its kind and lays the groundwork for future UEOPL-c
 ompleteness proofs.  This talk will provide an overview of the reduction fr
 om the problem Unique-End-of-Potential-Line to One-Permutation-Discrete-Con
 traction as well as correcting some errors that were done in the original p
 aper. 
DTSTAMP:20210104T182400
DTSTART:20210125T141500
CLASS:PUBLIC
LOCATION:online
SEQUENCE:0
SUMMARY:Michaela Borzechowski: One-Permutation-Discrete-Contraction is UEOP
 L-hard
UID:107739295@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20210125-L-Borzechowski.html
END:VEVENT
END:VCALENDAR