{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T17:53:45Z","timestamp":1790790825397,"version":"4.1.0"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>The existence of polynomial-time algorithms for the solution of parity games is a major open problem. The fastest known algorithms for the problem are randomized algorithms that run in subexponential time. These algorithms are all ultimately based on the randomized subexponential simplex algorithms of Kalai and of Matou\u0161ek, Sharir, and Welzl. Randomness seems to play an essential role in these algorithms. We use a completely different, and elementary, approach to obtain a deterministic subexponential algorithm for the solution of parity games. The new algorithm, like the existing randomized subexponential algorithms, uses only polynomial space, and it is almost as fast as the randomized subexponential algorithms mentioned above.<\/jats:p>","DOI":"10.1137\/070686652","type":"journal-article","created":{"date-parts":[[2008,11,12]],"date-time":"2008-11-12T18:07:19Z","timestamp":1226513239000},"page":"1519-1532","source":"Crossref","is-referenced-by-count":54,"title":["A Deterministic Subexponential Algorithm for Solving Parity Games"],"prefix":"10.1137","volume":"38","author":[{"given":"Marcin","family":"Jurdzi\u0144ski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mike","family":"Paterson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uri","family":"Zwick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,11,12]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.04.029"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"H. Bj\u00f6rklund, S. Sandberg, and S. Vorobyov,\n                      A discrete subexponential algorithm for parity games\n                      , in Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Comput. Sci. 2607, Springer, Berlin, 2003, pp. 663\u2013674.","DOI":"10.1007\/3-540-36494-3_58"},{"key":"R3","unstructured":"K. Chatterjee, M. Jurdzi\u0144ski, and T. A. Henzinger,\n                      Quantitative stochastic parity games\n                      , in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2004, pp. 114\u2013123."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"X. Chen and X. Deng,\n                      Settling the complexity of two-player Nash equilibrium\n                      , in Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, 2006, pp. 261\u2013272.","DOI":"10.1109\/FOCS.2006.69"},{"key":"R5","unstructured":"E. M. Clarke, O. Grumberg, and D. Peled,\n                      Model Checking\n                      , MIT Press, Cambridge, MA, 1999."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"A. Condon,\n                      On algorithms for simple stochastic games\n                      , in Advances in Computational Complexity Theory, AMS, Providence, RI, 1993, pp. 51\u201373.","DOI":"10.1090\/dimacs\/013\/04"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou,\n                      The complexity of computing a Nash equilibrium\n                      , in Proceedings of the 38th ACM Symposium on Theory of Computing (STOC), ACM Press, New York, 2006, pp. 71\u201378.","DOI":"10.1145\/1132516.1132527"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.009"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"E. A. Emerson,\n                      Model checking and mu-calculus\n                      , in Descriptive Complexity and Finite Models, N. Immerman and P. G. Kolaitis, eds., DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 31, AMS, Providence, RI, 1996, pp. 185\u2013214.","DOI":"10.1090\/dimacs\/031\/06"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"E. A. Emerson and C. Jutla,\n                      Tree automata, $\\mu$-calculus, and determinacy\n                      , in Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, 1991, pp. 368\u2013377.","DOI":"10.1109\/SFCS.1991.185392"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"E. A. Emerson, C. S. Jutla, and A. P. Sistla,\n                      On model-checking for fragments of $\\mu$-calculus\n                      , in Computer-Aided Verification (CAV), Lecture Notes in Comput. Sci. 697, Springer, Berlin, 1993, pp. 385\u2013396.","DOI":"10.1007\/3-540-56922-7_32"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10034"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"B. G\u00e4rtner and L. R\u00fcst,\n                      Simple stochastic games and P-matrix generalized linear complementarity problems\n                      , in Fundamentals of Computation Theory (FCT), Lecture Notes in Comput. Sci. 3623, Springer, Berlin, 2005, pp. 209\u2013220.","DOI":"10.1007\/11537311_19"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del, W. Thomas, and T. Wilke, eds.\n                      Automata, Logics, and Infinite Games. A Guide to Current Research\n                      , Lecture Notes in Comput. Sci. 2500, Springer, Berlin, 2002.","DOI":"10.1007\/3-540-36387-4"},{"key":"R16","unstructured":"N. Halman,\n                      Discrete and Lexicographic Helly Theorems and Their Relations to LP-type Problems\n                      , Ph.D. thesis, Tel Aviv University, Tel Aviv, Israel, 2004."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"R18","unstructured":"B. Juba,\n                      On the Hardness of Simple Stochastic Games\n                      , M.S. thesis, Carnegie Mellon University, Pittsburgh, PA, 2005."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00150-1"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"M. Jurdzi\u0144ski,\n                      Small progress measures for solving parity games\n                      , in Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Comput. Sci. 1770, Springer, Berlin, 2000, pp. 290\u2013301.","DOI":"10.1007\/3-540-46541-3_24"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"M. Jurdzi\u0144ski and R. Savani,\n                      A simple P-matrix linear complementarity problem for discounted games\n                      , in Computability in Europe (CiE), Lecture Notes in Comput. Sci. 5028, Springer, Berlin, 2008, pp. 283\u2013293.","DOI":"10.1007\/978-3-540-69407-6_32"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"M. Jurdzi\u0144ski, M. Paterson, and U. Zwick,\n                      A deterministic subexponential algorithm for solving parity games\n                      , in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2006, pp. 117\u2013123.","DOI":"10.1145\/1109557.1109571"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"G. Kalai,\n                      A subexponential randomized simplex algorithm (extended abstract)\n                      , in Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, New York, 1992, pp. 475\u2013482.","DOI":"10.1145\/129712.129759"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"V. King, O. Kupferman, and M. Y. Vardi,\n                      On the complexity of parity word automata\n                      , in Foundations of Software Science and Computation Structures (FoSSaCS), Lecture Notes in Comput. Sci. 2030, Springer, Berlin, 2001, pp. 276\u2013286.","DOI":"10.1007\/3-540-45315-6_18"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1035"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940877"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90036-D"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"J. Obdr\u017e\u00e1lek,\n                      Fast mu-calculus model checking when tree-width is bounded\n                      , in Computer-Aided Verification (CAV), Lecture Notes in Comput. Sci. 2725, Springer, Berlin, 2003, pp. 80\u201392.","DOI":"10.1007\/978-3-540-45069-6_7"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"S. Schewe,\n                      Solving parity games in big steps\n                      , in Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Lecture Notes in Comput. Sci. 4855, Springer, Berlin, 2007, pp. 449\u2013460.","DOI":"10.1007\/978-3-540-77050-3_37"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"O. Svensson and S. Vorobyov,\n                      Linear complementarity and P-matrices for stochastic games\n                      , in Perspectives of Systems Informatics, Andrei Ershov Memorial Conference (PSI 2006), Lecture Notes in Comput. Sci. 4378, Springer, Berlin, 2007, pp. 409\u2013423.","DOI":"10.1007\/978-3-540-70881-0_35"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"J. V\u00f6ge and M. Jurdzi\u0144ski,\n                      A discrete strategy improvement algorithm for solving parity games (extended abstract)\n                      , in Computer-Aided Verification (CAV), Lecture Notes in Comput. Sci. 1855, Springer, Berlin, 2000, pp. 202\u2013215.","DOI":"10.1007\/10722167_18"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00009-7"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00188-3"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070686652","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:19:23Z","timestamp":1787336363000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070686652"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/070686652"],"URL":"https:\/\/doi.org\/10.1137\/070686652","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}