Skip to main content

Publications

What type of publication do you want to show?

2024

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

DOI
10.4230/LIPIcs.ICALP.2024.32
Journal article

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

Conference Paper

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

Conference Paper

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

DOI
10.1609/aaai.v37i5.25695
Conference Paper

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

DOI
10.1145/3568163
Journal article

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.

Journal article

2022

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/

Journal article

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

DOI
10.1145/3519935.3520079
Conference Paper

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

Conference Paper

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

DOI
10.1016/j.jcss.2020.10.006
Conference Paper

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

DOI
10.1016/j.jcss.2020.05.007
Journal article

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

DOI
10.1038/s41598-020-71856-4
Journal article

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

Journal article

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

Conference Paper

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

Conference Paper

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

Conference Paper

2019

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

Other

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

DOI
10.23638/LMCS-14(4:9)2018
Journal article

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/

Other

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

Other

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

Conference Paper

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

Conference Paper

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

Conference Paper

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

Other

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

Other

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

DOI
10.1007/s00453-015-0078-7
Journal article

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.

Journal article

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

Conference Paper

2016

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

Conference Paper

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

DOI
10.1287/moor.2019.0993
Report

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/

Conference Paper

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

Report

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

DOI
10.1016/j.jcss.2015.02.005
Journal article

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

DOI
10.1007/978-3-662-53354-3_2
Journal article

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/

Journal article

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

DOI
10.1007/978-3-319-20086-6_26
Conference Paper

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

Conference Paper

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/

Conference Paper

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

DOI
10.1145/2600057.2602847
Conference Paper

The Complexity of the Simplex Method.

Fearnley, J., & Savani, R. (2014). The Complexity of the Simplex Method.. CoRR, abs/1404.0605.

Journal article

2013

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/

Conference Paper

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

DOI
10.2168/LMCS-9(2:06)2013
Journal article

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

DOI
10.1007/978-3-642-33996-7_10
Conference Paper

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

DOI
10.1007/978-3-642-33386-6_18
Journal article

Bounded Satisfiability for PCTL

Bertrand, N., Fearnley, J., & Schewe, S. (2012). Bounded Satisfiability for PCTL. Retrieved from http://arxiv.org/abs/1204.0469v1

Conference Paper

Synthesis of Succinct Systems

Fearnley, J., Peled, D., & Schewe, S. (2012). Synthesis of Succinct Systems. Retrieved from http://arxiv.org/abs/1202.5449v2

Conference Paper

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/

Conference Paper

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

DOI
10.4230/LIPIcs.FSTTCS.2011.399
Conference Paper

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

DOI
10.1007/978-3-642-22993-0_29
Conference Paper

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.

Conference Paper

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

Thesis / Dissertation

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

DOI
10.1007/978-3-642-17511-4_13
Conference Paper

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

DOI
10.1007/978-3-642-14162-1_46
Conference Paper

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

Conference Paper

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

Conference Paper

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.

Conference Paper

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

Conference Paper

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/

Conference Paper