The Library
Universal trees grow inside separating automata : quasi-polynomial lower bounds for parity games
Tools
Czerwiński, Wojciech, Daviaud, Laure, Fijalkow, Nathanael, Jurdzinski, Marcin, Lazic, Ranko and Parys, Pawel (2019) Universal trees grow inside separating automata : quasi-polynomial lower bounds for parity games. In: ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), California, 6-9 Jan 2019. Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 2333-2349. ISBN 9781611975482. doi:10.1137/1.9781611975482.142
|
PDF
WRAP-universal-trees-grow-inside-separating-automata-Lazic-2018.pdf - Accepted Version - Requires a PDF viewer. Download (703Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611975482.142
Abstract
Several distinct techniques have been proposed to design quasi-polynomial algorithms for solving parity games since the breakthrough result of Calude, Jain, Khoussainov, Li, and Stephan (2017): play summaries, progress measures and register games. We argue that all those techniques can be viewed as instances of the separation approach to solving parity games, a key technical component of which is constructing (explicitly or implicitly) an automaton that separates languages of words encoding plays that are (decisively) won by either of the two players. Our main technical result is a quasi-polynomial lower bound on the size of such separating automata that nearly matches the current best upper bounds. This forms a barrier that all existing approaches must overcome in the ongoing quest for a polynomial-time algorithm for solving parity games. The key and fundamental concept that we introduce and study is a universal ordered tree. The technical highlights are a quasi-polynomial lower bound on the size of universal ordered trees and a proof that every separating safety automaton has a universal tree hidden in its state space.
Item Type: | Conference Item (Paper) | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Game theory, Polynomials, Algorithms | |||||||||||||||
Journal or Publication Title: | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | |||||||||||||||
Publisher: | ACM | |||||||||||||||
ISBN: | 9781611975482 | |||||||||||||||
Official Date: | 2 January 2019 | |||||||||||||||
Dates: |
|
|||||||||||||||
Page Range: | pp. 2333-2349 | |||||||||||||||
DOI: | 10.1137/1.9781611975482.142 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Reuse Statement (publisher, data, author rights): | © The Authors and ACM 2019. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, http://dx.doi.org/10.1137/1.9781611975482.142 | |||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||
Date of first compliant deposit: | 1 November 2018 | |||||||||||||||
Date of first compliant Open Access: | 4 February 2019 | |||||||||||||||
Funder: | Narodowe Centrum Nauki [Polish National Science Center] | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Conference Paper Type: | Paper | |||||||||||||||
Title of Event: | ACM-SIAM Symposium on Discrete Algorithms (SODA 2019) | |||||||||||||||
Type of Event: | Conference | |||||||||||||||
Location of Event: | California | |||||||||||||||
Date(s) of Event: | 6-9 Jan 2019 | |||||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year