Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Succinct progress measures for solving parity games

Tools
- Tools
+ Tools

Jurdzinski, Marcin and Lazic, Ranko (2017) Succinct progress measures for solving parity games. In: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Reykjavik, Iceland, 20-23 Jun 2017. Published in: Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) pp. 1-9. ISBN 9781509030187. doi:10.1109/LICS.2017.8005092

[img]
Preview
PDF
WRAP-succinct-progress-measures-parity-games-Lazic-2017.pdf - Accepted Version - Requires a PDF viewer.

Download (654Kb) | Preview
Official URL: https://doi.org/10.1109/LICS.2017.8005092

Request Changes to record.

Abstract

The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasipolynomial 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.

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science)
Divisions: Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH): Computer science -- Mathematics, Directed graphs
Series Name: Annual Symposium on Logic in Computer Science
Journal or Publication Title: Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Publisher: ACM ; IEEE
ISBN: 9781509030187
Official Date: 2017
Dates:
DateEvent
2017Published
18 August 2017Available
22 March 2017Accepted
Page Range: pp. 1-9
Article Number: 32
DOI: 10.1109/LICS.2017.8005092
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Conference Paper Type: Paper
Title of Event: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Type of Event: Conference
Location of Event: Reykjavik, Iceland
Date(s) of Event: 20-23 Jun 2017
Related URLs:
  • Organisation
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us