John Fearnley

ORCID

Publication Activity (10 Years)

Years Active: 2009-2024
Publications (10 Years): 71

Top Venues

CoRR

J. Comput. Syst. Sci.

Algorithmica

ICALP

University of Warwick, Coventry, UK (PHD)

Education History

University of Warwick, Coventry, UK

PHD

Publications

Michaela Borzechowski, John Fearnley, Spencer Gordon, Rahul Savani, Patrick Schnider, Simon Weber
Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents. CoRR (2024)
Nathanaël Fijalkow, Nathalie Bertrand, Patricia Bouyer-Decitre, Romain Brenguier, Arnaud Carayol, John Fearnley, Hugo Gimbert, Florian Horn, Rasmus Ibsen-Jensen, Nicolas Markey, Benjamin Monmege, Petr Novotný, Mickael Randour, Ocan Sankur, Sylvain Schmitz, Olivier Serre, Mateusz Skomra
Games on Graphs. CoRR (2023)
Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos
Tight Inapproximability for Graphical Games. AAAI (2023)
John Fearnley, Paul Goldberg, Alexandros Hollender, Rahul Savani
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS. J. ACM 70 (1) (2023)
John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani
The Complexity of Computing KKT Solutions of Quadratic Programs. CoRR (2023)
Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos
Pure-Circuit: Strong Inapproximability for PPAD. FOCS (2022)
Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos
Pure-Circuit: Strong Inapproximability for PPAD. CoRR (2022)
Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos
Constant inapproximability for PPA. STOC (2022)
John Fearnley, Dömötör Pálvölgyi, Rahul Savani
A Faster Algorithm for Finding Tarski Fixed Points. ACM Trans. Algorithms 18 (3) (2022)
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, Paul G. Spirakis
Approximating the existential theory of the reals. J. Comput. Syst. Sci. 125 (2022)
Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos
Tight Inapproximability for Graphical Games. CoRR (2022)
Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos
Constant Inapproximability for PPA. CoRR (2022)
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos
Pizza Sharing Is PPA-Hard. AAAI (2022)
John Fearnley, Rahul Savani
A Faster Algorithm for Finding Tarski Fixed Points. STACS (2021)
John Fearnley, Martin Gairing, Matthias Mnich, Rahul Savani
Reachability Switching Games. Log. Methods Comput. Sci. 17 (2) (2021)
John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani
The complexity of gradient descent: CLS = PPAD ∩ PLS. STOC (2021)
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, Paul G. Spirakis
Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. J. Comput. Syst. Sci. 117 (2021)
Argyrios Deligkas, John Fearnley, Rahul Savani
Tree Polymatrix Games are PPAD-hard. CoRR (2020)
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos
Square-Cut Pizza Sharing is PPA-complete. CoRR (2020)
Argyrios Deligkas, John Fearnley, Paul G. Spirakis
Lipschitz Continuity and Approximate Equilibria. Algorithmica 82 (10) (2020)
John Fearnley, Rasmus Ibsen-Jensen, Rahul Savani
One-Clock Priced Timed Games are PSPACE-hard. CoRR (2020)
Argyrios Deligkas, John Fearnley, Rahul Savani
Tree Polymatrix Games Are PPAD-Hard. ICALP (2020)
John Fearnley, Rasmus Ibsen-Jensen, Rahul Savani
One-Clock Priced Timed Games are PSPACE-hard. LICS (2020)
Yann Disser, John Fearnley, Martin Gairing, Oliver Göbel, Max Klimm, Daniel Schmand, Alexander Skopalik, Andreas Tönnis
Hiring Secretaries over Time: The Benefit of Concurrent Employment. Math. Oper. Res. 45 (1) (2020)
John Fearnley, Rahul Savani
A faster algorithm for finding Tarski fixed points. CoRR (2020)
John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS. CoRR (2020)
John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani
Unique end of potential line. J. Comput. Syst. Sci. 114 (2020)
John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani
Unique End of Potential Line. ICALP (2019)
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, Paul G. Spirakis
Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. CoRR (2019)
John Fearnley, Sanjay Jain, Bart de Keijzer, Sven Schewe, Frank Stephan, Dominik Wojtczak
An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space. Int. J. Softw. Tools Technol. Transf. 21 (3) (2019)
Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis, John Fearnley, Marcin Jurdzinski, Rahul Savani
Distributed Methods for Computing Approximate Equilibria. Algorithmica 81 (3) (2019)
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, Paul G. Spirakis
Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. ICALP (2019)
Thomas Spooner, John Fearnley, Rahul Savani, Andreas Koukorinis
Market Making via Reinforcement Learning. AAMAS (2018)
Georgios Amanatidis, George Christodoulou, John Fearnley, Evangelos Markakis, Christos-Alexandros Psomas, Eftychia Vakaliou
An Improved Envy-Free Cake Cutting Protocol for Four Agents. SAGT (2018)
John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani
Unique End of Potential Line. CoRR (2018)
Argyrios Deligkas, John Fearnley, Rahul Savani
Inapproximability results for constrained approximate Nash equilibria. Inf. Comput. 262 (2018)
Georgios Amanatidis, George Christodoulou, John Fearnley, Evangelos Markakis, Christos-Alexandros Psomas, Eftychia Vakaliou
An Improved Envy-Free Cake Cutting Protocol for Four Agents. CoRR (2018)
John Fearnley, Martin Gairing, Matthias Mnich, Rahul Savani
Reachability Switching Games. ICALP (2018)
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, Paul G. Spirakis
Approximating the Existential Theory of the Reals. WINE (2018)
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, Paul G. Spirakis
Approximating the Existential Theory of the Reals. CoRR (2018)
John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani
End of Potential Line. CoRR (2018)
Thomas Spooner, John Fearnley, Rahul Savani, Andreas Koukorinis
Market Making via Reinforcement Learning. CoRR (2018)
John Fearnley, Rahul Savani
The Complexity of All-switches Strategy Improvement. Log. Methods Comput. Sci. 14 (4) (2018)
Argyrios Deligkas, John Fearnley, Rahul Savani
Computing Constrained Approximate Equilibria in Polymatrix Games. SAGT (2017)
John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, Dominik Wojtczak
An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space. CoRR (2017)
Argyrios Deligkas, John Fearnley, Rahul Savani
Computing Constrained Approximate Equilibria in Polymatrix Games. CoRR (2017)
John Fearnley, Martin Gairing, Matthias Mnich, Rahul Savani
Reachability Switching Games. CoRR (2017)
John Fearnley
Efficient Parallel Strategy Improvement for Parity Games. CoRR (2017)
John Fearnley
Efficient Parallel Strategy Improvement for Parity Games. CAV (2) (2017)
Argyrios Deligkas, John Fearnley, Rahul Savani, Paul G. Spirakis
Computing Approximate Nash Equilibria in Polymatrix Games. Algorithmica 77 (2) (2017)
John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, Dominik Wojtczak
An ordered approach to solving parity games in quasi polynomial time and quasi linear space. SPIN (2017)
John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani
CLS: New Problems and Completeness. CoRR (2017)
John Fearnley, Rahul Savani
Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries. ACM Trans. Economics and Comput. 4 (4) (2016)
Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis, John Fearnley, Marcin Jurdzinski, Rahul Savani
Distributed Methods for Computing Approximate Equilibria. WINE (2016)
Yann Disser, John Fearnley, Martin Gairing, Oliver Göbel, Max Klimm, Daniel Schmand, Alexander Skopalik, Andreas Tönnis
Hiring Secretaries over Time: The Benefit of Concurrent Employment. CoRR (2016)
Argyrios Deligkas, John Fearnley, Tobenna Peter Igwe, Rahul Savani
An Empirical Study on Computing Equilibria in Polymatrix Games. CoRR (2016)
John Fearnley, Markus N. Rabe, Sven Schewe, Lijun Zhang
Efficient approximation of optimal control for continuous-time Markov games. Inf. Comput. 247 (2016)
John Fearnley, Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen
Approximate Well-supported Nash Equilibria Below Two-thirds. Algorithmica 76 (2) (2016)
Argyrios Deligkas, John Fearnley, Rahul Savani
Inapproximability Results for Approximate Nash Equilibria. CoRR (2016)
Argyrios Deligkas, John Fearnley, Tobenna Peter Igwe, Rahul Savani
An Empirical Study on Computing Equilibria in Polymatrix Games. AAMAS (2016)
John Fearnley, Rahul Savani
The Complexity of All-switches Strategy Improvement. SODA (2016)
Argyrios Deligkas, John Fearnley, Rahul Savani
Inapproximability Results for Approximate Nash Equilibria. WINE (2016)
Argyrios Deligkas, John Fearnley, Paul G. Spirakis
Lipschitz Continuity and Approximate Equilibria. SAGT (2016)
John Fearnley, Rahul Savani
The Complexity of the Simplex Method. STOC (2015)
John Fearnley, Marcin Jurdzinski
Reachability in two-clock timed automata is PSPACE-complete. Inf. Comput. 243 (2015)
John Fearnley, Martin Gairing, Paul W. Goldberg, Rahul Savani
Learning equilibria of games via payoff queries. J. Mach. Learn. Res. 16 (2015)
John Fearnley, Tobenna Peter Igwe, Rahul Savani
An Empirical Study of Finding Approximate Equilibria in Bimatrix Games. SEA (2015)
John Fearnley, Rahul Savani
The Complexity of All-switches Strategy Improvement. CoRR (2015)
Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis, John Fearnley, Marcin Jurdzinski, Rahul Savani
Distributed Methods for Computing Approximate Equilibria. CoRR (2015)
John Fearnley, Doron A. Peled, Sven Schewe
Synthesis of succinct systems. J. Comput. Syst. Sci. 81 (7) (2015)
John Fearnley, Tobenna Peter Igwe, Rahul Savani
An Empirical Study of Finding Approximate Equilibria in Bimatrix Games. CoRR (2015)
John Fearnley, Rahul Savani
Finding approximate Nash equilibria of bimatrix games via payoff queries. EC (2014)
Argyrios Deligkas, John Fearnley, Rahul Savani, Paul G. Spirakis
Computing Approximate Nash Equilibria in Polymatrix Games. WINE (2014)
Argyrios Deligkas, John Fearnley, Rahul Savani, Paul G. Spirakis
Computing Approximate Nash Equilibria in Polymatrix Games. CoRR (2014)
John Fearnley, Rahul Savani
The Complexity of the Simplex Method. CoRR (2014)
John Fearnley, Sven Schewe
Time and Space Results for Parity Games with Bounded Treewidth Log. Methods Comput. Sci. 9 (2) (2013)
John Fearnley, Marcin Jurdzinski
Reachability in Two-Clock Timed Automata is PSPACE-complete CoRR (2013)
John Fearnley, Rahul Savani
Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries. CoRR (2013)
John Fearnley, Martin Gairing, Paul W. Goldberg, Rahul Savani
Learning Equilibria of Games via Payoff Queries CoRR (2013)
John Fearnley, Marcin Jurdzinski
Reachability in Two-Clock Timed Automata Is PSPACE-Complete. ICALP (2) (2013)
John Fearnley, Martin Gairing, Paul W. Goldberg, Rahul Savani
Learning equilibria of games via payoff queries. EC (2013)
Nathalie Bertrand, John Fearnley, Sven Schewe
Bounded Satisfiability for PCTL. CSL (2012)
John Fearnley, Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen
Approximate Well-Supported Nash Equilibria Below Two-Thirds. SAGT (2012)
John Fearnley, Doron A. Peled, Sven Schewe
Synthesis of Succinct Systems. ATVA (2012)
John Fearnley, Doron A. Peled, Sven Schewe
Synthesis of Succinct Systems CoRR (2012)
Nathalie Bertrand, John Fearnley, Sven Schewe
Bounded Satisfiability for PCTL CoRR (2012)
John Fearnley, Martin Zimmermann
Playing Muller Games in a Hurry. Int. J. Found. Comput. Sci. 23 (3) (2012)
John Fearnley, Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen
Approximate Well-supported Nash Equilibria below Two-thirds CoRR (2012)
John Fearnley, Sven Schewe
Time and Parallelizability Results for Parity Games with Bounded Treewidth. ICALP (2) (2012)
John Fearnley, Oded Lachish
Parity Games on Graphs with Medium Tree-Width. MFCS (2011)
John Fearnley, Markus N. Rabe, Sven Schewe, Lijun Zhang
Efficient Approximation of Optimal Control for Continuous-Time Markov Games. FSTTCS (2011)
John Fearnley, Martin Zimmermann
Playing Muller Games in a Hurry GANDALF (2010)
John Fearnley, Marcin Jurdzinski, Rahul Savani
Linear Complementarity Algorithms for Infinite Games. SOFSEM (2010)
John Fearnley
Non-oblivious Strategy Improvement CoRR (2010)
John Fearnley
Exponential Lower Bounds For Policy Iteration CoRR (2010)
John Fearnley
Non-oblivious Strategy Improvement. LPAR (Dakar) (2010)
John Fearnley
Exponential Lower Bounds for Policy Iteration. ICALP (2) (2010)
John Fearnley, Marcin Jurdzinski, Rahul Savani
Linear Complementarity Algorithms for Infinite Games CoRR (2009)

John Fearnley.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

John Fearnley