BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: The complexity classes Unique End of Potential Line (UEOPL) an
 d its promise version PUEOPL were introduced in 2018 by Fearnly et al. PUEO
 PL captures search problems where the instances are promised to have a uniq
 ue solution. UEOPL captures total search versions of these promise problems
 . The promise problems can be made total by defining violations that are re
 turned as a short certificate of an unfulfilled promise.    GridUSO is the 
 problem of finding the sink in a grid with a unique sink orientation. It wa
 s introduced by Gärtner et al. in 2008. We describe a promise preserving re
 duction from GridUSO to UniqueForwardEOPL\, a UEOPL-complete problem. Thus\
 , we show that GridUSO is in UEOPL and its promise version is in PUEOPL. 
DTSTAMP:20220621T212200
DTSTART:20220627T160000
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9 
 \n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Michaela Borzechowski (Freie Universität Berlin): Unique Sink Orien
 tations of Grids is in Unique End of Potential Line
UID:107920495@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20220627-C-Borzechowski.html
END:VEVENT
END:VCALENDAR