Succinct progress measures for solving parity games
- Prelegent(ci)
- Ranko Lazic
- Afiliacja
- University of Warwick
- Termin
- 15 listopada 2017 14:15
- Pokój
- p. 5050
- Seminarium
- Seminarium „Teoria automatów”
The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasi-polynomial time, where previously the best algorithms were mildly subexponential. 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.