JFJohn Fearnley

John Fearnley

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


John Fearnley has a total of 35 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD

    by Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos

  • Open Access

    The Complexity of Sparse Win-Lose Bimatrix Games

    by Eleni Batziou, John Fearnley, Abheek Ghosh, Rahul Savani

    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

    The Complexity of Computing KKT Solutions of Quadratic Programs

    by John Fearnley, Paul Goldberg, Alexandros Hollender, Rahul Savani

    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

    Monotone Contractions

    by Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani


  • Open Access

    Pizza Sharing is PPA-hard

    by Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos

    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.

  • Constant Inapproximability for PPA

    by Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos

    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

    Pure-Circuit: Tight Inapproximability for PPAD

    by Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos

    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

    Constant Inapproximability for Fisher Markets

    by Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos

    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

    The Complexity of Computing KKT Solutions of Quadratic Programs

    by John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani

    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

    by Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos

    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.