BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T013826Z
UID:Seminar-dept-444@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20170620T130000
DTEND:20170620T140000
SUMMARY:School Seminar Series
DESCRIPTION:Prof. Frank Stephan: Deciding Parity Games in Quasipolynomial Time\n\nIt is shown that the parity game can be solved in quasipolynomial\n\ntime. The parameterised parity game -- with n nodes\n\nand m distinct values (aka colours or priorities) --\n\nis proven to be in the class of fixed parameter tractable (FPT)\n\nproblems when parameterised over m.\n\nBoth results improve known bounds, from runtime\n\nn^{O(sqrtn)}$ to O(n^{log(m)+6})\n\nand from an XP-algorithm with runtime n^{m/3+O(1)}\n\nfor fixed parameter m to an FPT-algorithm with runtime O(n^5)+g(m),\n\nfor some function g depending on m only.\n\nAs an application it is proven that\n\ncoloured Muller games with $n$ nodes and $m$ colours can be decided\n\nin time O((m^m * n)^5); it is also shown that this bound cannot be\n\nimproved to 2^{o(m * \log(m))} * Poly(n) unless FPT = W[1].\n\nFurther investigations deal with memoryless Muller games and\n\nmulti-dimensional parity games.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=444
LOCATION:George Holt H223
END:VEVENT
END:VCALENDAR