Publications
2024
Pure-Circuit: Tight Inapproximability for PPAD
Deligkas, A., Fearnley, J., Hollender, A., & Melissourgos, T. (2024). Pure-Circuit: Tight Inapproximability for PPAD. In Journal of the ACM. Association for Computing Machinery (ACM). doi:10.1145/3678166
Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents
Borzechowski, M., Fearnley, J., Gordon, S., Savani, R., Schnider, P., & Weber, S. (2024). Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents. Leibniz International Proceedings in Informatics, LIPIcs, 297. doi:10.4230/LIPIcs.ICALP.2024.32
The Complexity of Computing KKT Solutions of Quadratic Programs
Fearnley, J., Goldberg, P. W., Hollender, A., & Savani, R. (2024). The Complexity of Computing KKT Solutions of Quadratic Programs. Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 892-903. doi:10.1145/3618260.3649647
The Complexity of Computing KKT Solutions of Quadratic Programs.
Fearnley, J., Goldberg, P. W., Hollender, A., & Savani, R. (2024). The Complexity of Computing KKT Solutions of Quadratic Programs.. In B. Mohar, I. Shinkar, & R. O'Donnell (Eds.), STOC (pp. 892-903). ACM. Retrieved from https://doi.org/10.1145/3618260
Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents.
Borzechowski, M., Fearnley, J., Gordon, S., Savani, R., Schnider, P., & Weber, S. (2024). Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents.. In K. Bringmann, M. Grohe, G. Puppis, & O. Svensson (Eds.), ICALP Vol. 297 (pp. 32:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from https://www.dagstuhl.de/dagpub/978-3-95977-322-5
2023
Tight Inapproximability for Graphical Games
Deligkas, A., Fearnley, J., Hollender, A., & Melissourgos, T. (n.d.). Tight Inapproximability for Graphical Games. In Proceedings of the AAAI Conference on Artificial Intelligence Vol. 37 (pp. 5600-5607). Association for the Advancement of Artificial Intelligence (AAAI). doi:10.1609/aaai.v37i5.25695
The Complexity of Gradient Descent: CLS = PPAD ∧ PLS
Fearnley, J., Goldberg, P., Hollender, A., & Savani, R. (2023). The Complexity of Gradient Descent: CLS = PPAD ∧ PLS. JOURNAL OF THE ACM, 70(1). doi:10.1145/3568163
Games on Graphs.
Fijalkow, N., Bertrand, N., Bouyer-Decitre, P., Brenguier, R., Carayol, A., Fearnley, J., . . . Skomra, M. (2023). Games on Graphs.. CoRR, abs/2305.10546.
2022
Pure-Circuit: Strong Inapproximability for PPAD
Deligkas, A., Fearnley, J., Alexandros, H., & Themistoklis, M. (2022). Pure-Circuit: Strong Inapproximability for PPAD. In FOCS 2022.
A Faster Algorithm for Finding Tarski Fixed Points
Fearnley, J., Palvolgyi, D., & Savani, R. (2022). A Faster Algorithm for Finding Tarski Fixed Points. ACM TRANSACTIONS ON ALGORITHMS, 18(3). doi:10.1145/3524044
A Faster Algorithm for Finding Tarski Fixed Points
Fearnley, J., Pálvölgyi, D., & Savani, R. (2022). A Faster Algorithm for Finding Tarski Fixed Points. ACM Transactions on Algorithms, 18(3), 1-23. doi:10.1145/3524044
Pizza Sharing Is PPA-Hard
Deligkas, A., Fearnley, J., & Melissourgos, T. (2022). Pizza Sharing Is PPA-Hard. THIRTY-SIXTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FOURTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE / THE TWELVETH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 4957-4965. Retrieved from https://www.webofscience.com/
Constant Inapproximability for PPA
Deligkas, A., Fearnley, J., Hollender, A., & Melissourgos, T. (2022). Constant Inapproximability for PPA. In PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22) (pp. 1010-1023). doi:10.1145/3519935.3520079
Approximating the existential theory of the reals
Deligkas, A., Fearnley, J., Melissourgos, T., & Spirakis, P. G. (2022). Approximating the existential theory of the reals. Journal of Computer and System Sciences, 125, 106-128. doi:10.1016/j.jcss.2021.11.002
Pizza Sharing Is PPA-Hard.
Deligkas, A., Fearnley, J., & Melissourgos, T. (2022). Pizza Sharing Is PPA-Hard.. In AAAI (pp. 4957-4965). AAAI Press. Retrieved from https://ojs.aaai.org/index.php/AAAI/issue/view/507
2021
Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
Deligkas, A., Fearnley, J., Melissourgos, T., & Spirakis, P. G. (2021). Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. In JOURNAL OF COMPUTER AND SYSTEM SCIENCES Vol. 117 (pp. 75-98). doi:10.1016/j.jcss.2020.10.006
REACHABILITY SWITCHING GAMES
Fearnley, J., Gairing, M., Mnich, M., & Savani, R. (2021). REACHABILITY SWITCHING GAMES. In LOGICAL METHODS IN COMPUTER SCIENCE Vol. 17. doi:10.23638/LMCS-17(2:10)2021
Reachability switching games
Fearnley, J., Gairing, M., Mnich, M., & Savani, A. R. (2021). Reachability switching games. Logical Methods in Computer Science, 17(2), 10:1-10:29. doi:10.23638/LMCS-17(2:10)2021
2020
Unique End of Potential Line
Fearnley, J. S., Gordon, S., Mehta, R., & Savani, R. (2020). Unique End of Potential Line. Journal of Computer and System Sciences, 114, 1-35. doi:10.1016/j.jcss.2020.05.007
The Complexity of Gradient Descent: CLS = PPAD ∧ PLS
Fearnley, J., Goldberg, P. W., Hollender, A., & Savani, R. (2021). The Complexity of Gradient Descent: CLS = PPAD ∧ PLS. STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 46-59. doi:10.1145/3406325.3451052
A Faster Algorithm for Finding Tarski Fixed Points
Fearnley, J., & Savani, R. (2021). A Faster Algorithm for Finding Tarski Fixed Points. 38TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2021), 187. doi:10.4230/LIPIcs.STACS.2021.29
Lipschitz Continuity and Approximate Equilibria
Deligkas, A., Fearnley, J., & Spirakis, P. (2020). Lipschitz Continuity and Approximate Equilibria. In ALGORITHMICA Vol. 82 (pp. 2927-2954). doi:10.1007/s00453-020-00709-3
Bayesian optimisation of restriction zones for bluetongue control.
Spooner, T., Jones, A. E., Fearnley, J., Savani, R., Turner, J., & Baylis, M. (2020). Bayesian optimisation of restriction zones for bluetongue control.. Scientific Reports, 10(1), 15139. doi:10.1038/s41598-020-71856-4
One-Clock Priced Timed Games are PSPACE-hard
Fearnley, J., Ibsen-Jensen, R., & Savani, R. (2020). One-Clock Priced Timed Games are PSPACE-hard. LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science. Retrieved from http://arxiv.org/abs/2001.04458v2
Tree Polymatrix Games are PPAD-hard
Deligkas, A., Fearnley, J., & Savani, R. (2020). Tree Polymatrix Games are PPAD-hard. Retrieved from http://arxiv.org/abs/2002.12119v1
Hiring Secretaries over Time: The Benefit of Concurrent Employment
Disser, Y., Fearnley, J., Gairing, M., Goebel, O., Klimm, M., Schmand, D., . . . Toennis, A. (2020). Hiring Secretaries over Time: The Benefit of Concurrent Employment. Mathematics of Operations Research, 45(1), 323-352. doi:10.1287/moor.2019.0993
One-Clock Priced Timed Games are PSPACE-hard.
Fearnley, J., Ibsen-Jensen, R., & Savani, R. (2020). One-Clock Priced Timed Games are PSPACE-hard.. In H. Hermanns, L. Zhang, N. Kobayashi, & D. Miller (Eds.), LICS (pp. 397-409). ACM. Retrieved from https://doi.org/10.1145/3373718
Tree Polymatrix Games Are PPAD-Hard.
Deligkas, A., Fearnley, J., & Savani, R. (2020). Tree Polymatrix Games Are PPAD-Hard.. In A. Czumaj, A. Dawar, & E. Merelli (Eds.), ICALP Vol. 168 (pp. 38:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from https://www.dagstuhl.de/dagpub/978-3-95977-138-2
2019
Distributed Methods for Computing Approximate Equilibria
Czumaj, A., Deligkas, A., Fasoulakis, M., Fearnley, J. S., Jurdzinski, M., & Savani, R. (2019). Distributed Methods for Computing Approximate Equilibria. Algorithmica: an international journal in computer science, 81, 1205-1231. doi:10.1007/s00453-018-0465-y
Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
Deligkas, A., Fearnley, J., Melissourgos, T., & Spirakis, P. G. (2019). Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. Retrieved from http://arxiv.org/abs/1903.03101v2
2018
Unique End of Potential Line
Fearnley, J., Gordon, S., Mehta, R., & Savani, R. (2018). Unique End of Potential Line. Retrieved from http://arxiv.org/abs/1811.03841v1
The Complexity of All-Switches Strategy Improvement
Fearnley, J. S., & Savani, R. S. J. (2018). The Complexity of All-Switches Strategy Improvement. Logical Methods in Computer Science, 14(4), 1-57. doi:10.23638/LMCS-14(4:9)2018
Approximating the Existential Theory of the Reals
Deligkas, A., Fearnley, J., Melissourgos, T., & Spirakis, P. G. (2018). Approximating the Existential Theory of the Reals. In WEB AND INTERNET ECONOMICS, WINE 2018 Vol. 11316 (pp. 126-139). doi:10.1007/978-3-030-04612-5_9
Inapproximability results for constrained approximate Nash equilibria
Deligkas, A., Fearnley, J. S., & Savani, R. (2018). Inapproximability results for constrained approximate Nash equilibria. Information and Computation, 262(1), 40-56. doi:10.1016/j.ic.2018.06.001
An Improved Envy-Free Cake Cutting Protocol for Four Agents
Amanatidis, G., Christodoulou, G., Fearnley, J., Markakis, E., Psomas, C. -A., & Vakaliou, E. (2018). An Improved Envy-Free Cake Cutting Protocol for Four Agents. In Lecture Notes in Computer Science. Beijing, China: Springer Nature. doi:10.1007/978-3-319-99660-8_9
Market Making via Reinforcement Learning
Spooner, T., Fearnley, J., Savani, R., & Koukorinis, A. (2018). Market Making via Reinforcement Learning. In PROCEEDINGS OF THE 17TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS (AAMAS' 18) (pp. 434-442). Retrieved from https://www.webofscience.com/
End of Potential Line
Fearnley, J., Gordon, S., Mehta, R., & Savani, R. (2018). End of Potential Line. Retrieved from http://arxiv.org/abs/1804.03450v2
An Improved Envy-Free Cake Cutting Protocol for Four Agents.
Amanatidis, G., Christodoulou, G., Fearnley, J., Markakis, E., Psomas, C. -A., & Vakaliou, E. (2018). An Improved Envy-Free Cake Cutting Protocol for Four Agents.. In X. Deng (Ed.), SAGT Vol. 11059 (pp. 87-99). Springer. Retrieved from https://doi.org/10.1007/978-3-319-99660-8
Approximating the Existential Theory of the Reals.
Deligkas, A., Fearnley, J., Melissourgos, T., & Spirakis, P. G. (2018). Approximating the Existential Theory of the Reals.. In G. Christodoulou, & T. Harks (Eds.), WINE Vol. 11316 (pp. 126-139). Springer. Retrieved from https://doi.org/10.1007/978-3-030-04612-5
Market Making via Reinforcement Learning.
Spooner, T., Fearnley, J., Savani, R., & Koukorinis, A. (2018). Market Making via Reinforcement Learning.. In E. André, S. Koenig, M. Dastani, & G. Sukthankar (Eds.), AAMAS (pp. 434-442). International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA / ACM. Retrieved from http://dl.acm.org/citation.cfm?id=3237383
2017
Reachability Switching Games
Fearnley, J., Gairing, M., Mnich, M., & Savani, R. (2017). Reachability Switching Games. In April (Vol. 22, pp. 2021). Retrieved from http://dx.doi.org/10.23638/LMCS-17(2:10)2021
Computing Constrained Approximate Equilibria in Polymatrix Games
Deligkas., Fearnley., & Savani, R. S. J. (2017). Computing Constrained Approximate Equilibria in Polymatrix Games. In Symposium on Algorithmic Game Theory (SAGT) (pp. 93-105). doi:10.1007/978-3-319-66700-3_8
An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space
Fearnley, J., Jain, S., Schewe, S., Stephan, F., & Wojtczak, D. (2017). An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space. In SPIN'17: PROCEEDINGS OF THE 24TH ACM SIGSOFT INTERNATIONAL SPIN SYMPOSIUM ON MODEL CHECKING OF SOFTWARE (pp. 112-121). doi:10.1145/3092282.3092286
Efficient Parallel Strategy Improvement for Parity Games
Fearnley, J. S. (2017). Efficient Parallel Strategy Improvement for Parity Games. In R. Majumdar, & V. Kunčak (Eds.), Computer Aided Verification. CAV 2017, Lecture Notes in Computer Science Proceedings, Part II Vol. 10427 (pp. 137-154). Heidelberg, Germany. doi:10.1007/978-3-319-63390-9_8
An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space.
Fearnley, J., Jain, S., Schewe, S., Stephan, F., & Wojtczak, D. (2017). An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space.. CoRR, abs/1703.01296.
CLS: New Problems and Completeness
Fearnley, J., Gordon, S., Mehta, R., & Savani, R. (2017). CLS: New Problems and Completeness. Retrieved from http://arxiv.org/abs/1702.06017v2
Computing Approximate Nash Equilibria in Polymatrix Games
Deligkas, A., Fearnley, J., Savani, R., & Spirakis, P. (2017). Computing Approximate Nash Equilibria in Polymatrix Games. ALGORITHMICA, 77(2), 487-514. doi:10.1007/s00453-015-0078-7
Computing Approximate Nash Equilibria in Polymatrix Games.
Deligkas, A., Fearnley, J., Savani, R., & Spirakis, P. G. (2017). Computing Approximate Nash Equilibria in Polymatrix Games.. Algorithmica, 77, 487-514.
Computing Constrained Approximate Equilibria in Polymatrix Games.
Deligkas, A., Fearnley, J., & Savani, R. (2017). Computing Constrained Approximate Equilibria in Polymatrix Games.. CoRR, abs/1705.02266.
Efficient Parallel Strategy Improvement for Parity Games.
Fearnley, J. (2017). Efficient Parallel Strategy Improvement for Parity Games.. In R. Majumdar, & V. Kuncak (Eds.), CAV (2) Vol. 10427 (pp. 137-154). Springer. Retrieved from https://doi.org/10.1007/978-3-319-63390-9
2016
Distributed Methods for Computing Approximate Equilibria
Czumaj, A., Deligkas, A., Fasoulakis, M., Fearnley, J. S., Jurdzinski, M., & Savani, R. (2016). Distributed Methods for Computing Approximate Equilibria. In Lecture Notes in Computer Science Vol. 10123. Berlin: Springer Nature. doi:10.1007/978-3-662-54110-4_2
Inapproximability Results for Approximate Nash Equilibria.
Deligkas, A., Fearnley, J., & Savani, R. (2016). Inapproximability Results for Approximate Nash Equilibria.. In Y. Cai, & A. Vetta (Eds.), WINE Vol. 10123 (pp. 29-43). Springer. Retrieved from https://doi.org/10.1007/978-3-662-54110-4
Inapproximability Results for Approximate Nash Equilibria
Deligkas, A., Fearnley, J., & Savani, R. (2016). Inapproximability Results for Approximate Nash Equilibria. Retrieved from http://arxiv.org/abs/1608.03574v3
Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries
Fearnley, J., & Savani, R. (2016). Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries. ACM Transactions on Economics and Computation (TEAC), 4(4). doi:10.1145/2956579
Hiring Secretaries over Time: The Benefit of Concurrent Employment
Disser, Y., Fearnley, J., Gairing, M., Goebel, O., Klimm, M., Schmand, D., . . . Toennis, A. (2020). Hiring Secretaries over Time: The Benefit of Concurrent Employment. doi:10.1287/moor.2019.0993
Efficient approximation of optimal control for continuous-time Markov games
Fearnley, J., Rabe, M. N., Schewe, S., & Zhang, L. (2016). Efficient approximation of optimal control for continuous-time Markov games. INFORMATION AND COMPUTATION, 247, 106-129. doi:10.1016/j.ic.2015.12.002
An Empirical Study on Computing Equilibria in Polymatrix Games
Deligkas, A., Fearnley, J., Igwe, T. P., & Savani, R. (2016). An Empirical Study on Computing Equilibria in Polymatrix Games. In AAMAS'16: PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS (pp. 186-195). Retrieved from https://www.webofscience.com/
An Empirical Study on Computing Equilibria in Polymatrix Games.
Deligkas, A., Fearnley, J., Igwe, T. P., & Savani, R. (2016). An Empirical Study on Computing Equilibria in Polymatrix Games..
The Complexity of All-Switches Strategy Improvement
Fearnley, J., & Savani, R. (2016). The Complexity of All-Switches Strategy Improvement. In R. Krauthgamer (Ed.), Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 130-139). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611974331.ch10
2015
Synthesis of succinct systems
Fearnley, J., Peled, D., & Schewe, S. (2015). Synthesis of succinct systems. Journal of Computer and System Sciences, 81(7), 1171-1193. doi:10.1016/j.jcss.2015.02.005
Lipschitz Continuity and Approximate Equilibria
Deligkas, A., Fearnley, J., & Spirakis, P. (2016). Lipschitz Continuity and Approximate Equilibria. ALGORITHMIC GAME THEORY, SAGT 2016, 9928, 15-26. doi:10.1007/978-3-662-53354-3_2
Learning Equilibria of Games via Payoff Queries
Fearnley, J., Gairing, M., Goldberg, P. W., & Savani, R. (2015). Learning Equilibria of Games via Payoff Queries. JOURNAL OF MACHINE LEARNING RESEARCH, 16, 1305-1344. Retrieved from https://www.webofscience.com/
Reachability in Two-Clock Timed Automata is PSPACE-complete
Fearnley, J., & Jurdzinski, M. (2015). Reachability in Two-Clock Timed Automata is PSPACE-complete. Information and Computation, 243, 26-36. doi:10.1016/j.ic.2014.12.004
An Empirical Study of Finding Approximate Equilibria in Bimatrix Games
Fearnley, J., Igwe, T. P., & Savani, R. (2015). An Empirical Study of Finding Approximate Equilibria in Bimatrix Games. In EXPERIMENTAL ALGORITHMS, SEA 2015 Vol. 9125 (pp. 339-351). doi:10.1007/978-3-319-20086-6_26
An Empirical Study of Finding Approximate Equilibria in Bimatrix Games.
Fearnley, J., Igwe, T. P., & Savani, R. (2015). An Empirical Study of Finding Approximate Equilibria in Bimatrix Games.. In E. Bampis (Ed.), SEA Vol. 9125 (pp. 339-351). Springer. Retrieved from https://doi.org/10.1007/978-3-319-20086-6
2014
Computing Approximate Nash Equilibria in Polymatrix Games
Deligkas, A., Fearnley, J., Savani, R., & Spirakis, P. (2014). Computing Approximate Nash Equilibria in Polymatrix Games. In WEB AND INTERNET ECONOMICS Vol. 8877 (pp. 58-71). Retrieved from https://www.webofscience.com/
The Complexity of the Simplex Method
Fearnley, J., & Savani, R. (2015). The Complexity of the Simplex Method. In STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (pp. 201-208). doi:10.1145/2746539.2746558
Finding approximate nash equilibria of bimatrix games via payoff queries
Fearnley, J., & Savani, R. (2014). Finding approximate nash equilibria of bimatrix games via payoff queries. In Proceedings of the fifteenth ACM conference on Economics and computation (pp. 657-674). ACM. doi:10.1145/2600057.2602847
The Complexity of the Simplex Method.
Fearnley, J., & Savani, R. (2014). The Complexity of the Simplex Method.. CoRR, abs/1404.0605.
2013
Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries
Fearnley, J., & Savani, R. (2013). Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries. Retrieved from http://arxiv.org/abs/1310.7419v2
Reachability in Two-Clock Timed Automata Is PSPACE-Complete
Fearnley, J., & Jurdzinski, M. (2013). Reachability in Two-Clock Timed Automata Is PSPACE-Complete. In AUTOMATA, LANGUAGES, AND PROGRAMMING, PT II Vol. 7966 (pp. 212-223). Retrieved from https://www.webofscience.com/
TIME AND PARALLELIZABILITY RESULTS FOR PARITY GAMES WITH BOUNDED TREE AND DAG WIDTH
Fearnley, J., & Schewe, S. (2013). TIME AND PARALLELIZABILITY RESULTS FOR PARITY GAMES WITH BOUNDED TREE AND DAG WIDTH. LOGICAL METHODS IN COMPUTER SCIENCE, 9(2). doi:10.2168/LMCS-9(2:06)2013
Learning Equilibria of Games via Payoff Queries
Fearnley, J., Gairing, M., Goldberg, P., & Savani, R. (2013). Learning Equilibria of Games via Payoff Queries. Retrieved from http://arxiv.org/abs/1302.3116v4
Reachability in Two-Clock Timed Automata is PSPACE-complete
Fearnley, J., & Jurdziński, M. (2013). Reachability in Two-Clock Timed Automata is PSPACE-complete. Retrieved from http://dx.doi.org/10.1016/j.ic.2014.12.004
2012
Approximate Well-Supported Nash Equilibria Below Two-Thirds
Fearnley, J., Goldberg, P. W., Savani, R., & Sørensen, T. B. (2012). Approximate Well-Supported Nash Equilibria Below Two-Thirds. In Unknown Conference (pp. 108-119). Springer Berlin Heidelberg. doi:10.1007/978-3-642-33996-7_10
Synthesis of Succinct Systems
Fearnley, J., Peled, D., & Schewe, S. (2012). Synthesis of Succinct Systems. Unknown Journal, 208-222. doi:10.1007/978-3-642-33386-6_18
Approximate Well-supported Nash Equilibria Below Two-thirds
Fearnley, J., Goldberg, P. W., Savani, R., & Sørensen, T. B. (2016). Approximate Well-supported Nash Equilibria Below Two-thirds. Algorithmica, 76, 297-319. doi:10.1007/s00453-015-0029-3
PLAYING MULLER GAMES IN A HURRY
Fearnley, J., & Zimmermann, M. (2012). PLAYING MULLER GAMES IN A HURRY. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 23(3), 649-668. doi:10.1142/S0129054112400321
Bounded Satisfiability for PCTL
Bertrand, N., Fearnley, J., & Schewe, S. (2012). Bounded Satisfiability for PCTL. Retrieved from http://arxiv.org/abs/1204.0469v1
Synthesis of Succinct Systems
Fearnley, J., Peled, D., & Schewe, S. (2012). Synthesis of Succinct Systems. Retrieved from http://arxiv.org/abs/1202.5449v2
Time and Parallelizability Results for Parity Games with Bounded Treewidth
Fearnley, J., & Schewe, S. (2012). Time and Parallelizability Results for Parity Games with Bounded Treewidth. In AUTOMATA, LANGUAGES, AND PROGRAMMING, ICALP 2012, PT II Vol. 7392 (pp. 189-200). Retrieved from https://www.webofscience.com/
2011
Efficient approximation of optimal control for continuous-time Markov games
Fearnley, J., Rabe, M., Schewe, S., & Zhang, L. (2011). Efficient approximation of optimal control for continuous-time Markov games. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 13 (pp. 399-410). doi:10.4230/LIPIcs.FSTTCS.2011.399
Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width
Fearnley, J., & Schewe, S. (2011). Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width. Logical Methods in Computer Science, Volume 9, Issue 2 (June 18, 2013) lmcs:791. Retrieved from http://dx.doi.org/10.2168/LMCS-9(2:6)2013
Parity Games on Graphs with Medium Tree-Width
Fearnley, J., & Lachish, O. (2011). Parity Games on Graphs with Medium Tree-Width. In Unknown Conference (pp. 303-314). Springer Berlin Heidelberg. doi:10.1007/978-3-642-22993-0_29
Efficient Approximation of Optimal Control for Continuous-Time Markov Games
Fearnley, J., Rabe, M., Schewe, S., & Zhang, L. (2011). Efficient Approximation of Optimal Control for Continuous-Time Markov Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (pp. (Accepted)). Bombay: Leibniz International Proceedings in Informatics.
Strategy iteration algorithms for games and Markov decision processes
Fearnley, J. (2011). Strategy iteration algorithms for games and Markov decision processes. (PhD Thesis, The University of Warwick).
2010
Non-oblivious strategy improvement
Fearnley, J. (2010). Non-oblivious strategy improvement. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 6355 LNAI (pp. 212-230). doi:10.1007/978-3-642-17511-4_13
Efficient Approximation of Optimal Control for Markov Games
Fearnley, J., Rabe, M., Schewe, S., & Zhang, L. (2010). Efficient Approximation of Optimal Control for Markov Games. Retrieved from http://arxiv.org/abs/1011.0397v2
Exponential Lower Bounds for Policy Iteration
Fearnley, J. (2010). Exponential Lower Bounds for Policy Iteration. In Unknown Conference (pp. 551-562). Springer Berlin Heidelberg. doi:10.1007/978-3-642-14162-1_46
Playing Muller Games in a Hurry
Fearnley, J., & Zimmermann, M. (2010). Playing Muller Games in a Hurry. In EPTCS 25, 2010, pp. 146-161. Retrieved from http://dx.doi.org/10.4204/EPTCS.25.15
Exponential Lower Bounds For Policy Iteration
Fearnley, J. (2010). Exponential Lower Bounds For Policy Iteration. Retrieved from http://arxiv.org/abs/1003.3418v1
Non-oblivious Strategy Improvement
Fearnley, J. (2010). Non-oblivious Strategy Improvement. Retrieved from http://dx.doi.org/10.1007/978-3-642-17511-4_13
Linear complementarity algorithms for infinite games
Fearnley, J., Jurdziński, M., & Savani, R. (2010). Linear complementarity algorithms for infinite games. In 36th Conference on Current Trends in Theory and Practice of Computer Science (pp. 382-393). Czech Republic: Springer-Verlag.
Playing Muller games in a hurry
Fearnley, J., & Zimmermann, M. (2010). Playing Muller games in a hurry. In First International Symposium on Games, Automata, Logics and Formal Verification (pp. 146-162). Minori: EPTCS. Retrieved from http://eptcs.org/content.cgi?GANDALF10
2009
Linear Complementarity Algorithms for Infinite Games
Fearnley, J., Jurdzinski, M., & Savani, R. (2010). Linear Complementarity Algorithms for Infinite Games. In SOFSEM 2010: THEORY AND PRACTICE OF COMPUTER SCIENCE, PROCEEDINGS Vol. 5901 (pp. 382-+). Retrieved from https://www.webofscience.com/