| 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. |