John Fearnley
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
John Fearnley has a total of 35 co-authors. Here are the top co-authors by number of shared publications:
- Rahul Savani
University of Liverpool
16 shared publications - Argyrios Deligkas
Royal Holloway, University of London
12 shared publications - Themistoklis Melissourgos
University of Essex, Colchester, United Kingdom
9 shared publications - Alexandros Hollender
University of Oxford, UK
8 shared publications - Paul G. Spirakis
University of Liverpool
4 shared publications - Paul W. Goldberg
University of Oxford
4 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1049-1060
Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1049-1060
Open AccessFisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
- Open Access
The Complexity of Sparse Win-Lose Bimatrix Games
We prove that computing an $ε$-approximate Nash equilibrium of a win-lose bimatrix game with constant sparsity is PPAD-hard for inverse-polynomial $ε$. Our result holds for 3-sparse games, which is tight given that 2-sparse win-lose bimatrix games can be solved in polynomial time.Open AccessThe Complexity of Sparse Win-Lose Bimatrix Games
We prove that computing an $ε$-approximate Nash equilibrium of a win-lose bimatrix game with constant sparsity is PPAD-hard for inverse-polynomial $ε$. Our result holds for 3-sparse games, which is tight given that 2-sparse win-lose bimatrix games can be solved in polynomial time. - Open Access
- 9 October 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (5) , 1-48
The Complexity of Computing KKT Solutions of Quadratic Programs
It is well known that solving a (non-convex) quadratic program is NP -hard. We show that the problem remains hard even if we are only looking for a Karush–Kuhn–Tucker (KKT) point, instead of a global optimum. Namely, we prove that computing a KKT point of a quadratic polynomial over the domain [0,1] n is complete for the class CLS = PPAD ∩ PLS .
- 9 October 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (5) , 1-48
Open AccessThe Complexity of Computing KKT Solutions of Quadratic Programs
It is well known that solving a (non-convex) quadratic program is NP -hard. We show that the problem remains hard even if we are only looking for a Karush–Kuhn–Tucker (KKT) point, instead of a global optimum. Namely, we prove that computing a KKT point of a quadratic polynomial over the domain [0,1] n is complete for the class CLS = PPAD ∩ PLS .
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 507-517
Monotone Contractions
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 507-517
Open AccessMonotone Contractions
- Open Access
- 21 April 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Pizza Sharing is PPA-hard
We study the computational complexity of finding a solution for the straight-cut and square-cut pizza sharing problems. We show that computing an ε-approximate solution is PPA -complete for both problems, while finding an exact solution for the square-cut problem is FIXP -hard. Our PPA -hardness results apply for any ε < 1/5, even when all mass distributions consist of non-overlapping axis-aligned rectangles or when they are point sets, and our FIXP -hardness result applies even when all mass distributions are unions of squares and right-angled triangles. We also prove that the decision variants of both approximate problems are NP -complete, while the decision variant for the exact version of square-cut pizza sharing is \(\exists \mathbb {R} \) -complete.- 21 April 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Open AccessPizza Sharing is PPA-hard
We study the computational complexity of finding a solution for the straight-cut and square-cut pizza sharing problems. We show that computing an ε-approximate solution is PPA -complete for both problems, while finding an exact solution for the square-cut problem is FIXP -hard. Our PPA -hardness results apply for any ε < 1/5, even when all mass distributions consist of non-overlapping axis-aligned rectangles or when they are point sets, and our FIXP -hardness result applies even when all mass distributions are unions of squares and right-angled triangles. We also prove that the decision variants of both approximate problems are NP -complete, while the decision variant for the exact version of square-cut pizza sharing is \(\exists \mathbb {R} \) -complete. - 11 February 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 54 (1) , 163-192
Constant Inapproximability for PPA
In the [Formula: see text]-Consensus-Halving problem, we are given [Formula: see text] probability measures [Formula: see text] on the interval [Formula: see text], and the goal is to partition [Formula: see text] into two parts [Formula: see text] and [Formula: see text] using at most [Formula: see text] cuts, so that [Formula: see text] for all [Formula: see text]. This fundamental fair division problem was the first natural problem shown to be complete for the class PPA , and all subsequent PPA -completeness results for other natural problems have been obtained by reducing from it. We show that [Formula: see text]-Consensus-Halving is PPA -complete even when the parameter [Formula: see text] is a constant. In fact, we prove that this holds for any constant [Formula: see text]. As a result, we obtain constant inapproximability results for all known natural PPA -complete problems, including necklace splitting, the discrete ham sandwich problem, two variants of the pizza sharing problem, and for finding fair independent sets in cycles and paths.
- 11 February 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 54 (1) , 163-192
Constant Inapproximability for PPA
In the [Formula: see text]-Consensus-Halving problem, we are given [Formula: see text] probability measures [Formula: see text] on the interval [Formula: see text], and the goal is to partition [Formula: see text] into two parts [Formula: see text] and [Formula: see text] using at most [Formula: see text] cuts, so that [Formula: see text] for all [Formula: see text]. This fundamental fair division problem was the first natural problem shown to be complete for the class PPA , and all subsequent PPA -completeness results for other natural problems have been obtained by reducing from it. We show that [Formula: see text]-Consensus-Halving is PPA -complete even when the parameter [Formula: see text] is a constant. In fact, we prove that this holds for any constant [Formula: see text]. As a result, we obtain constant inapproximability results for all known natural PPA -complete problems, including necklace splitting, the discrete ham sandwich problem, two variants of the pizza sharing problem, and for finding fair independent sets in cycles and paths.
- Open Access
- 5 October 2024
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 71 (5) , 1-48
Pure-Circuit: Tight Inapproximability for PPAD
The current state-of-the-art methods for showing inapproximability in PPAD arise from the ɛ-Generalized-Circuit (ɛ- GCircuit ) problem. Rubinstein (2018) showed that there exists a small unknown constant ɛ for which ɛ- GCircuit is PPAD -hard, and subsequent work has shown hardness results for other problems in PPAD by using ɛ- GCircuit as an intermediate problem. We introduce Pure-Circuit , a new intermediate problem for PPAD , which can be thought of as ɛ- GCircuit pushed to the limit as ɛ → 1, and we show that the problem is PPAD -complete. We then prove that ɛ- GCircuit is PPAD -hard for all ɛ < 1/10 by a reduction from Pure-Circuit , and thus strengthen all prior work that has used GCircuit as an intermediate problem from the existential-constant regime to the large-constant regime. We show that stronger inapproximability results can be derived by reducing directly from Pure-Circuit . In particular, we prove tight inapproximability results for computing approximate Nash equilibria and approximate well-supported Nash equilibria in graphical games, for finding approximate well-supported Nash equilibria in polymatrix games, and for finding approximate equilibria in threshold games.
- 5 October 2024
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 71 (5) , 1-48
Open AccessPure-Circuit: Tight Inapproximability for PPAD
The current state-of-the-art methods for showing inapproximability in PPAD arise from the ɛ-Generalized-Circuit (ɛ- GCircuit ) problem. Rubinstein (2018) showed that there exists a small unknown constant ɛ for which ɛ- GCircuit is PPAD -hard, and subsequent work has shown hardness results for other problems in PPAD by using ɛ- GCircuit as an intermediate problem. We introduce Pure-Circuit , a new intermediate problem for PPAD , which can be thought of as ɛ- GCircuit pushed to the limit as ɛ → 1, and we show that the problem is PPAD -complete. We then prove that ɛ- GCircuit is PPAD -hard for all ɛ < 1/10 by a reduction from Pure-Circuit , and thus strengthen all prior work that has used GCircuit as an intermediate problem from the existential-constant regime to the large-constant regime. We show that stronger inapproximability results can be derived by reducing directly from Pure-Circuit . In particular, we prove tight inapproximability results for computing approximate Nash equilibria and approximate well-supported Nash equilibria in graphical games, for finding approximate well-supported Nash equilibria in polymatrix games, and for finding approximate equilibria in threshold games.
- Open Access
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 13-39
Constant Inapproximability for Fisher Markets
We study the problem of computing approximate market equilibria in Fisher markets with separable piecewise-linear concave (SPLC) utility functions. In this setting, the problem was only known to be PPAD-complete for inverse-polynomial approximations. We strengthen this result by showing PPAD-hardness for constant approximations. This means that the problem does not admit a polynomial time approximation scheme (PTAS) unless PPAD = P. In fact, we prove that computing any approximation better than 1/11 is PPAD-complete. As a direct byproduct of our main result, we get the same inapproximability bound for Arrow-Debreu exchange markets with SPLC utility functions.
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 13-39
Open AccessConstant Inapproximability for Fisher Markets
We study the problem of computing approximate market equilibria in Fisher markets with separable piecewise-linear concave (SPLC) utility functions. In this setting, the problem was only known to be PPAD-complete for inverse-polynomial approximations. We strengthen this result by showing PPAD-hardness for constant approximations. This means that the problem does not admit a polynomial time approximation scheme (PTAS) unless PPAD = P. In fact, we prove that computing any approximation better than 1/11 is PPAD-complete. As a direct byproduct of our main result, we get the same inapproximability bound for Arrow-Debreu exchange markets with SPLC utility functions.
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 892-903
The Complexity of Computing KKT Solutions of Quadratic Programs
It is well known that solving a (non-convex) quadratic program is NP-hard. We show that the problem remains hard even if we are only looking for a Karush-Kuhn-Tucker (KKT) point, instead of a global optimum. Namely, we prove that computing a KKT point of a quadratic polynomial over the domain [0,1]n is complete for the class CLS = PPAD∩PLS.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 892-903
Open AccessThe Complexity of Computing KKT Solutions of Quadratic Programs
It is well known that solving a (non-convex) quadratic program is NP-hard. We show that the problem remains hard even if we are only looking for a Karush-Kuhn-Tucker (KKT) point, instead of a global optimum. Namely, we prove that computing a KKT point of a quadratic polynomial over the domain [0,1]n is complete for the class CLS = PPAD∩PLS.
- Open Access
Pizza Sharing is PPA-hard
We study the computational complexity of finding a solution for the straight-cut and square-cut pizza sharing problems. We show that computing an $\varepsilon$-approximate solution is PPA-complete for both problems, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. Our PPA-hardness results apply for any $\varepsilon < 1/5$, even when all mass distributions consist of non-overlapping axis-aligned rectangles or when they are point sets, and our FIXP-hardness result applies even when all mass distributions are unions of squares and right-angled triangles. We also prove that the decision variants of both approximate problems are NP-complete, while it is ETR-complete for the exact version of square-cut pizza sharing.Open AccessPizza Sharing is PPA-hard
We study the computational complexity of finding a solution for the straight-cut and square-cut pizza sharing problems. We show that computing an $\varepsilon$-approximate solution is PPA-complete for both problems, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. Our PPA-hardness results apply for any $\varepsilon < 1/5$, even when all mass distributions consist of non-overlapping axis-aligned rectangles or when they are point sets, and our FIXP-hardness result applies even when all mass distributions are unions of squares and right-angled triangles. We also prove that the decision variants of both approximate problems are NP-complete, while it is ETR-complete for the exact version of square-cut pizza sharing.