Universal trees grow inside separating automata : quasi-polynomial lower bounds for parity games
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 5976
- Type
- E - Conference contribution
- DOI
-
10.1137/1.9781611975482.142
- Title of conference / published proceedings
- ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)
- First page
- 2333
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- January
- Year of publication
- 2019
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
5
- Research group(s)
-
T - Theory and Foundations
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The reach of this work, published at the top algorithms conference, spans the algorithms and logic communities. Its main result is central in a £750k EPSRC project, and its techniques have transformed the study of parity games (Colcombet&Fijalkow FoSSaCS'19 keynote, Parys CSL'20, Daviaud et al. ICALP'20), mean-payoff games (Fijalkow et al. MFCS’20), and automata (Daviaud et al. CONCUR'19). This research also spurred Parys's breakthrough work (MFCS'19 Best Paper), led to invited presentations at international scientific events (including GandALF'19, IMS Singapore, Simons Institute Berkeley) and seminars (including LSE, Oxford, Paris 7), and is taught in graduate courses (Bordeaux, Paris, St Petersburg).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -