Edit Profile (opens in new tab) Fearnley, John Co-Author Distance Author ID: fearnley.john Published as: Fearnley, John Documents Indexed: 48 Publications since 2010, including 3 Additional arXiv Preprints Co-Authors: 37 Co-Authors with 45 Joint Publications 1,125 Co-Co-Authors all top 5 Co-Authors 3 single-authored 23 Savani, Rahul 15 Deligkas, Argyrios 8 Spirakis, Paul G. 7 Schewe, Sven 6 Melissourgos, Themistoklis 5 Goldberg, Paul W. 5 Jurdziński, Marcin 4 Gairing, Martin 3 Gordon, Spencer L. 3 Hollender, Alexandros 2 Czumaj, Artur 2 Fasoulakis, Michail 2 Mehta, Ruta 2 Mnich, Matthias 2 Peled, Doron A. 2 Rabe, Markus N. 2 Sørensen, Troels Bjerre 2 Zhang, Lijun 2 Zimmermann, Martín G. 1 Amanatidis, Georgios 1 Bertrand, Nathalie 1 Borzechowski, Michaela 1 Christodoulou, George C. 1 Disser, Yann 1 Göbel, Oliver 1 Ibsen-Jensen, Rasmus 1 Klimm, Max 1 Lachish, Oded 1 Markakis, Evangelos 1 Pálvölgyi, Dömötör 1 Psomas, Christos-Alexandros 1 Schmand, Daniel 1 Schnider, Patrick 1 Skopalik, Alexander 1 Tönnis, Andreas 1 Vakaliou, Eftychia 1 Weber, Simon all top 5 Serials 4 Journal of Computer and System Sciences 4 Algorithmica 3 Information and Computation 3 Logical Methods in Computer Science 1 Mathematics of Operations Research 1 International Journal of Foundations of Computer Science 1 Journal of Machine Learning Research (JMLR) 1 ACM Transactions on Algorithms all top 5 Fields 38 Computer science (68-XX) 31 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 3 Probability theory and stochastic processes (60-XX) 3 Operations research, mathematical programming (90-XX) 2 Algebraic topology (55-XX) 1 Mathematical logic and foundations (03-XX) 1 Statistics (62-XX) 1 Systems theory; control (93-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 40 Publications have been cited 213 times in 159 Documents Cited by ▼ Year ▼ Exponential lower bounds for policy iteration. Zbl 1288.68089 Fearnley, John 20 2010 Reachability in two-clock timed automata is PSPACE-complete. Zbl 1345.68155 Fearnley, John; Jurdziński, Marcin 18 2015 Learning equilibria of games via payoff queries. Zbl 1351.91008 Fearnley, John; Gairing, Martin; Goldberg, Paul W.; Savani, Rahul 15 2015 Unique end of potential line. Zbl 1461.68086 Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul 13 2020 Reachability in two-clock timed automata is PSPACE-complete. Zbl 1327.68118 Fearnley, John; Jurdziński, Marcin 13 2013 Approximate well-supported Nash equilibria below two-thirds. Zbl 1284.91018 Fearnley, John; Goldberg, Paul W.; Savani, Rahul; Sørensen, Troels Bjerre 12 2012 The complexity of the simplex method. Zbl 1321.90079 Fearnley, John; Savani, Rahul 10 2015 Non-oblivious strategy improvement. Zbl 1310.91040 Fearnley, John 9 2010 Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. Zbl 1477.68115 Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. 8 2021 Distributed methods for computing approximate equilibria. Zbl 1404.91003 Czumaj, Artur; Deligkas, Argyrios; Fasoulakis, Michail; Fearnley, John; Jurdziński, Marcin; Savani, Rahul 7 2016 An improved envy-free cake cutting protocol for four agents. Zbl 1415.91170 Amanatidis, Georgios; Christodoulou, George; Fearnley, John; Markakis, Evangelos; Psomas, Christos-Alexandros; Vakaliou, Eftychia 7 2018 The complexity of gradient descent: CLS = PPAD \(\cap\) PLS. Zbl 07765152 Fearnley, John; Goldberg, Paul W.; Hollender, Alexandros; Savani, Rahul 6 2021 Approximate well-supported Nash equilibria below two-thirds. Zbl 1347.91008 Fearnley, John; Goldberg, Paul W.; Savani, Rahul; Sørensen, Troels Bjerre 5 2016 Computing approximate Nash equilibria in polymatrix games. Zbl 1358.91007 Deligkas, Argyrios; Fearnley, John; Savani, Rahul; Spirakis, Paul 5 2017 Bounded satisfiability for PCTL. Zbl 1252.68189 Bertrand, Nathalie; Fearnley, John; Schewe, Sven 5 2012 Distributed methods for computing approximate equilibria. Zbl 1422.91052 Czumaj, Artur; Deligkas, Argyrios; Fasoulakis, Michail; Fearnley, John; Jurdziński, Marcin; Savani, Rahul 5 2019 The complexity of all-switches strategy improvement. Zbl 1417.91132 Fearnley, John; Savani, Rahul 5 2016 Computing approximate Nash equilibria in polymatrix games. Zbl 1404.91008 Deligkas, Argyrios; Fearnley, John; Savani, Rahul; Spirakis, Paul 4 2014 Inapproximability results for constrained approximate Nash equilibria. Zbl 1400.68086 Deligkas, Argyrios; Fearnley, John; Savani, Rahul 4 2018 Time and parallelizability results for parity games with bounded treewidth. Zbl 1367.68108 Fearnley, John; Schewe, Sven 4 2012 Approximating the existential theory of the reals. Zbl 1443.91012 Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. 4 2018 Efficient approximation of optimal control for continuous-time Markov games. Zbl 1337.91015 Fearnley, John; Rabe, Markus N.; Schewe, Sven; Zhang, Lijun 3 2016 Inapproximability results for approximate Nash equilibria. Zbl 1404.91004 Deligkas, Argyrios; Fearnley, John; Savani, Rahul 3 2016 Lipschitz continuity and approximate equilibria. Zbl 1403.91076 Deligkas, Argyrios; Fearnley, John; Spirakis, Paul 3 2016 Parity games on graphs with medium tree-width. Zbl 1343.91012 Fearnley, John; Lachish, Oded 2 2011 Playing Muller games in a hurry. Zbl 1246.91018 Fearnley, John; Zimmermann, Martin 2 2012 Computing constrained approximate equilibria in polymatrix games. Zbl 1403.91017 Deligkas, Argyrios; Fearnley, John; Savani, Rahul 2 2017 Time and parallelizability results for parity games with bounded tree and DAG width. Zbl 1266.68123 Fearnley, John; Schewe, Sven 2 2013 Lipschitz continuity and approximate equilibria. Zbl 1455.91064 Deligkas, Argyrios; Fearnley, John; Spirakis, Paul 2 2020 Reachability switching games. Zbl 1499.68200 Fearnley, John; Gairing, Martin; Mnich, Matthias; Savani, Rahul 2 2021 Unique end of potential line. Zbl 07561549 Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul 2 2019 Efficient parallel strategy improvement for parity games. Zbl 1494.91027 Fearnley, John 2 2017 Approximating the existential theory of the reals. Zbl 07466700 Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. 2 2022 Efficient approximation of optimal control for continuous-time Markov games. Zbl 1246.68165 Fearnley, John; Rabe, Markus; Schewe, Sven; Zhang, Lijun 1 2011 Linear complementarity algorithms for infinite games. Zbl 1274.91101 Fearnley, John; Jurdziński, Marcin; Savani, Rahul 1 2010 Synthesis of succinct systems. Zbl 1374.68282 Fearnley, John; Peled, Doron; Schewe, Sven 1 2012 One-clock priced timed games are PSPACE-hard. Zbl 07299484 Fearnley, John; Ibsen-Jensen, Rasmus; Savani, Rahul 1 2020 Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. Zbl 1498.68120 Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. 1 2019 Hiring secretaries over time: the benefit of concurrent employment. Zbl 1444.60032 Disser, Yann; Fearnley, John; Gairing, Martin; Göbel, Oliver; Klimm, Max; Schmand, Daniel; Skopalik, Alexander; Tönnis, Andreas 1 2020 Reachability switching games. Zbl 1499.68201 Fearnley, John; Gairing, Martin; Mnich, Matthias; Savani, Rahul 1 2018 Approximating the existential theory of the reals. Zbl 07466700 Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. 2 2022 Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. Zbl 1477.68115 Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. 8 2021 The complexity of gradient descent: CLS = PPAD \(\cap\) PLS. Zbl 07765152 Fearnley, John; Goldberg, Paul W.; Hollender, Alexandros; Savani, Rahul 6 2021 Reachability switching games. Zbl 1499.68200 Fearnley, John; Gairing, Martin; Mnich, Matthias; Savani, Rahul 2 2021 Unique end of potential line. Zbl 1461.68086 Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul 13 2020 Lipschitz continuity and approximate equilibria. Zbl 1455.91064 Deligkas, Argyrios; Fearnley, John; Spirakis, Paul 2 2020 One-clock priced timed games are PSPACE-hard. Zbl 07299484 Fearnley, John; Ibsen-Jensen, Rasmus; Savani, Rahul 1 2020 Hiring secretaries over time: the benefit of concurrent employment. Zbl 1444.60032 Disser, Yann; Fearnley, John; Gairing, Martin; Göbel, Oliver; Klimm, Max; Schmand, Daniel; Skopalik, Alexander; Tönnis, Andreas 1 2020 Distributed methods for computing approximate equilibria. Zbl 1422.91052 Czumaj, Artur; Deligkas, Argyrios; Fasoulakis, Michail; Fearnley, John; Jurdziński, Marcin; Savani, Rahul 5 2019 Unique end of potential line. Zbl 07561549 Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul 2 2019 Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. Zbl 1498.68120 Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. 1 2019 An improved envy-free cake cutting protocol for four agents. Zbl 1415.91170 Amanatidis, Georgios; Christodoulou, George; Fearnley, John; Markakis, Evangelos; Psomas, Christos-Alexandros; Vakaliou, Eftychia 7 2018 Inapproximability results for constrained approximate Nash equilibria. Zbl 1400.68086 Deligkas, Argyrios; Fearnley, John; Savani, Rahul 4 2018 Approximating the existential theory of the reals. Zbl 1443.91012 Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. 4 2018 Reachability switching games. Zbl 1499.68201 Fearnley, John; Gairing, Martin; Mnich, Matthias; Savani, Rahul 1 2018 Computing approximate Nash equilibria in polymatrix games. Zbl 1358.91007 Deligkas, Argyrios; Fearnley, John; Savani, Rahul; Spirakis, Paul 5 2017 Computing constrained approximate equilibria in polymatrix games. Zbl 1403.91017 Deligkas, Argyrios; Fearnley, John; Savani, Rahul 2 2017 Efficient parallel strategy improvement for parity games. Zbl 1494.91027 Fearnley, John 2 2017 Distributed methods for computing approximate equilibria. Zbl 1404.91003 Czumaj, Artur; Deligkas, Argyrios; Fasoulakis, Michail; Fearnley, John; Jurdziński, Marcin; Savani, Rahul 7 2016 Approximate well-supported Nash equilibria below two-thirds. Zbl 1347.91008 Fearnley, John; Goldberg, Paul W.; Savani, Rahul; Sørensen, Troels Bjerre 5 2016 The complexity of all-switches strategy improvement. Zbl 1417.91132 Fearnley, John; Savani, Rahul 5 2016 Efficient approximation of optimal control for continuous-time Markov games. Zbl 1337.91015 Fearnley, John; Rabe, Markus N.; Schewe, Sven; Zhang, Lijun 3 2016 Inapproximability results for approximate Nash equilibria. Zbl 1404.91004 Deligkas, Argyrios; Fearnley, John; Savani, Rahul 3 2016 Lipschitz continuity and approximate equilibria. Zbl 1403.91076 Deligkas, Argyrios; Fearnley, John; Spirakis, Paul 3 2016 Reachability in two-clock timed automata is PSPACE-complete. Zbl 1345.68155 Fearnley, John; Jurdziński, Marcin 18 2015 Learning equilibria of games via payoff queries. Zbl 1351.91008 Fearnley, John; Gairing, Martin; Goldberg, Paul W.; Savani, Rahul 15 2015 The complexity of the simplex method. Zbl 1321.90079 Fearnley, John; Savani, Rahul 10 2015 Computing approximate Nash equilibria in polymatrix games. Zbl 1404.91008 Deligkas, Argyrios; Fearnley, John; Savani, Rahul; Spirakis, Paul 4 2014 Reachability in two-clock timed automata is PSPACE-complete. Zbl 1327.68118 Fearnley, John; Jurdziński, Marcin 13 2013 Time and parallelizability results for parity games with bounded tree and DAG width. Zbl 1266.68123 Fearnley, John; Schewe, Sven 2 2013 Approximate well-supported Nash equilibria below two-thirds. Zbl 1284.91018 Fearnley, John; Goldberg, Paul W.; Savani, Rahul; Sørensen, Troels Bjerre 12 2012 Bounded satisfiability for PCTL. Zbl 1252.68189 Bertrand, Nathalie; Fearnley, John; Schewe, Sven 5 2012 Time and parallelizability results for parity games with bounded treewidth. Zbl 1367.68108 Fearnley, John; Schewe, Sven 4 2012 Playing Muller games in a hurry. Zbl 1246.91018 Fearnley, John; Zimmermann, Martin 2 2012 Synthesis of succinct systems. Zbl 1374.68282 Fearnley, John; Peled, Doron; Schewe, Sven 1 2012 Parity games on graphs with medium tree-width. Zbl 1343.91012 Fearnley, John; Lachish, Oded 2 2011 Efficient approximation of optimal control for continuous-time Markov games. Zbl 1246.68165 Fearnley, John; Rabe, Markus; Schewe, Sven; Zhang, Lijun 1 2011 Exponential lower bounds for policy iteration. Zbl 1288.68089 Fearnley, John 20 2010 Non-oblivious strategy improvement. Zbl 1310.91040 Fearnley, John 9 2010 Linear complementarity algorithms for infinite games. Zbl 1274.91101 Fearnley, John; Jurdziński, Marcin; Savani, Rahul 1 2010 all cited Publications top 5 cited Publications all top 5 Cited by 274 Authors 17 Fearnley, John 16 Goldberg, Paul W. 13 Deligkas, Argyrios 11 Savani, Rahul 7 Hollender, Alexandros 7 Schewe, Sven 6 Spirakis, Paul G. 5 Markey, Nicolas 5 Randour, Mickael 5 Rubinstein, Aviad 4 Clemente, Lorenzo 4 De Loera, Jesús A. 4 Fasoulakis, Michail 4 Filos-Ratsikas, Aris 4 Katzman, Matthew J. 4 Kiefer, Stefan 4 Lasota, Sławomir 4 Marmolejo Cossío, Francisco J. 4 Melissourgos, Themistoklis 4 Shirmohammadi, Mahsa 4 Suksompong, Warut 3 Bouyer, Patricia 3 Brihaye, Thomas 3 Chodil, Miroslav 3 Friedmann, Oliver 3 Göös, Mika 3 Hofman, Piotr 3 Jurdziński, Marcin 3 Kucera, Antonin 3 Mazowiecki, Filip 3 Parys, Paweł 3 Pérez, Guillermo A. 3 Wojtczak, Dominik 2 Ani, Joshua 2 Avni, Guy 2 Benerecetti, Massimo 2 Bitansky, Nir 2 Chen, Zhaohua 2 Czerwiński, Wojciech 2 Czumaj, Artur 2 Delgrange, Florent 2 Dell’Erba, Daniele 2 Delvenne, Jean-Charles 2 Demaine, Erik D. 2 Deng, Xiao-Tie 2 Fijalkow, Nathanaël 2 Gerencsér, Balázs 2 Gordon, Spencer L. 2 Guha, Shibashis 2 Hélouët, Loïc 2 Hendrickson, Dylan H. 2 Hollanders, Romain 2 Huang, Wenhan 2 Jungers, Raphaël M. 2 Křetínský, Jan 2 Kupferman, Orna 2 Larsen, Kim Guldstrand 2 Laursen, Simon 2 Li, Hanyu 2 Li, Yuhao 2 Ligett, Katrina 2 Lynch, Jayson 2 Manurangsi, Pasin 2 Markakis, Evangelos 2 Mayr, Richard M. 2 Mehta, Ruta 2 Mnich, Matthias 2 Mogavero, Fabio 2 Ouaknine, Joel O. 2 Oualhadj, Youssouf 2 Paneth, Omer 2 Piórkowski, Radosław 2 Rabinovich, Roman 2 Raha, Ritam 2 Segal-Halevi, Erel 2 Sørensen, Troels Bjerre 2 Totzke, Patrick 2 Turchetta, Stefano 2 Worrell, James B. 2 Wu, Zhiwei Steven 2 Ye, Yinyu 2 Zhang, Lijun 2 Zimmermann, Martín G. 1 Ah-Fat, Patrick 1 Ahmadi, Amir Ali 1 Akian, Marianne 1 Alexander, Kozachinskiy 1 Almagor, Shaull 1 Asarin, Eugene 1 Babichenko, Yakov 1 Baghoolizadeh, Shirin 1 Balaji, Nikhil 1 Barman, Siddharth 1 Belkhir, Walid 1 Bell, Paul C. 1 Berwanger, Dietmar 1 Bhaskar, Umang 1 Birmpas, Georgios 1 Black, Alexander E. 1 Blanchard, Moïse ...and 174 more Authors all top 5 Cited in 41 Serials 12 Theoretical Computer Science 10 Logical Methods in Computer Science 9 Journal of Computer and System Sciences 8 SIAM Journal on Computing 8 Information and Computation 5 Algorithmica 4 Games and Economic Behavior 4 Formal Methods in System Design 2 Artificial Intelligence 2 Discrete Applied Mathematics 2 Mathematics of Operations Research 2 SIAM Journal on Discrete Mathematics 2 Mathematical Programming. Series A. Series B 2 The Journal of Artificial Intelligence Research (JAIR) 1 Acta Informatica 1 Information Processing Letters 1 Journal of the Franklin Institute 1 Mathematics Magazine 1 Applied Mathematics and Computation 1 International Journal of Game Theory 1 Operations Research Letters 1 Journal of Symbolic Computation 1 Computers & Operations Research 1 European Journal of Operational Research 1 SIAM Journal on Optimization 1 Computational Complexity 1 Numerical Linear Algebra with Applications 1 Top 1 INFORMS Journal on Computing 1 Theory of Computing Systems 1 Optimization Methods & Software 1 Soft Computing 1 Mathematical Methods of Operations Research 1 Lobachevskii Journal of Mathematics 1 ACM Transactions on Computational Logic 1 Journal of Discrete Algorithms 1 Discrete Optimization 1 Optimization Letters 1 ACM Transactions on Algorithms 1 SIAM Journal on Applied Algebra and Geometry 1 CGT. Computing in Geometry and Topology all top 5 Cited in 15 Fields 119 Computer science (68-XX) 80 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 22 Operations research, mathematical programming (90-XX) 12 Mathematical logic and foundations (03-XX) 9 Combinatorics (05-XX) 4 Convex and discrete geometry (52-XX) 4 Probability theory and stochastic processes (60-XX) 4 Systems theory; control (93-XX) 3 Information and communication theory, circuits (94-XX) 2 Algebraic topology (55-XX) 2 Numerical analysis (65-XX) 1 History and biography (01-XX) 1 Operator theory (47-XX) 1 Geometry (51-XX) 1 Quantum theory (81-XX) Citations by Year