Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Marcin Jurdzinski: Succinct progress measures and solving parity games in quasi-polynomial time

LFCS seminar: Marcin Jurdzinski: Succinct progress measures and solving parity games in quasi-polynomial time

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
When May 09, 2017
from 04:00 PM to 05:00 PM
Where IF 4.31/4.33
Add event to calendar vCal
iCal
Abstract: The recent breakthrough paper by Calude et al. (a winner of STOC 2017 Best Paper Award) has given the first algorithm for solving parity games in quasi-polynomial time, where previously the best algorithms were mildly sub-exponential. We devise an alternative quasi-polynomial time algorithm based on progress measures, which allows us to reduce the space required from quasi-polynomial to nearly linear.  Our key technical tools are a novel concept of ordered tree coding, and a succinct tree coding result that we prove using bounded adaptive multi-counters, both of which are interesting in their own right.
 
Apart from presenting our technical work on succinct progress measures, I will survey the relevance of parity games to the theory and practice of computer-aided verification and synthesis, their surprising impact on broader theoretical computer science, the history of results and techniques used for solving parity games, and the recent advances in the state of the art.
 
This is joint work with Ranko Lazic.

Document Actions