BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260502T011236Z
UID:Seminar-verification-696@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Patrick Totzke:MAILTO:totzke@liverpool.ac.uk
DTSTART:20200414T110000
DTEND:20200414T120000
SUMMARY:Verification Series
DESCRIPTION:Rasmus Ibsen-Jensen: One-Clock Priced Timed Games are PSPACE-hard\n\nThe talk is about my recent result (with John Fearnley & Rahul Savani) on one-clock priced timed games, showing the first complexity lower bound (beyond P). The paper show that they are PSPACE-hard (the talk will only show NP- and coNP-hardness though) and that the value function (which are an piecewise linear function) consists of an exponential number of line pieces. The lower bound also applies in some special cases. As positive results, we show that trees and undirected graphs are in P.\n\nBased on joint work with John Fearnley & Rahul Savani\nSee https://arxiv.org/abs/2001.04458\nTo appear in LICS'20\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=696
LOCATION:
END:VEVENT
END:VCALENDAR