ACM Symposium on Theory of Computing, STOC 2017


Article Details
Title: Deciding parity games in quasipolynomial time
Article URLs:
Alternative Article URLs: http://www.comp.nus.edu.sg/~sanjay/paritygame.pdf http://www.comp.nus.edu.sg/~fstephan/paritygame.ps http://arxiv.org/abs/1703.01296 http://arxiv.org/abs/1702.05051
Authors: Cristian S. Calude
  • University of Auckland, Department of Computer Science Auckland 1142, New Zealand
Sanjay Jain
  • National University of Singapore, School of Computing
Bakhadyr Khoussainov
  • University of Auckland, Department of Computer Science
Wei Li
  • National University of Singapore, Department of Mathematics
Frank Stephan
  • National University of Singapore, Department of Mathematics
  • National University of Singapore, School of Computing
Sharing: Research produced no artifacts
Verification: Authors have verified information
Artifact Evaluation Badge: none
Artifact URLs:
Artifact Correspondence Email Addresses:
NSF Award Numbers:
DBLP Key: conf/stoc/CaludeJKL017
Author Comments: The links http://www.comp.nus.edu.sg/~sanjay/paritygame.pdf and http://www.comp.nus.edu.sg/~fstephan/paritygame.ps are long versions of the paper as submitted to the Special Issue of STOC 2017. The authors reserve the right to update the papers linked in the case that further improvements of the text are made. The links http://arxiv.org/abs/1703.01296 and http://arxiv.org/abs/1702.05051 are links to two follow-up papers which obtained algorithms not only running in quasipolynomial time but also in polynomial space. While the original algorithm is not implemented, the two follow-up algorithms have been implemented.

Discuss this paper and its artifacts below