27 citations · 187 across the 36 of their papers we have counts for
13 papers · 1 filter
Super Unique Tarski is in UEOPL
John Fearnley, Rahul Savani
We define the Super-Unique-Tarski problem, which is a Tarski instance in which all slices are required to have a unique fixed point. We show that Super-Unique-Tarski lies in UEOPL…
Monotone Contractions
Eleni Batziou, John Fearnley, Spencer Gordon +2
We study functions that are both monotone and contracting, and we consider the problem of finding an -approximate fixed point of $f…
Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents
Michaela Borzechowski, John Fearnley, Spencer Gordon +3
We provide polynomial-time reductions between three search problems from three distinct areas: the P-matrix linear complementarity problem (P-LCP), finding the sink of a unique sin…
The Complexity of Computing KKT Solutions of Quadratic Programs
John Fearnley, Paul W. Goldberg, Alexandros Hollender +1
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, i…
Pure-Circuit: Tight Inapproximability for PPAD
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
The current state-of-the-art methods for showing inapproximability in PPAD arise from the -Generalized-Circuit (-GCircuit) problem. Rubinstein (2018) show…
Constant Inapproximability for PPA
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
In the -Consensus-Halving problem, we are given probability measures on the interval , and the goal is to partition into two parts…
Pizza Sharing is PPA-hard
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…
The Complexity of Gradient Descent: CLS = PPAD PLS
John Fearnley, Paul W. Goldberg, Alexandros Hollender +1
We study search problems that can be solved by performing Gradient Descent on a bounded convex polytopal domain and show that this class is equal to the intersection of two well-kn…
Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos +1
We study the problem of finding an exact solution to the consensus halving problem. While recent work has shown that the approximate version of this problem is PPA-complete, we sho…
Unique End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta +1
This paper studies the complexity of problems in PPAD PLS that have unique solutions. Three well-known examples of such problems are the problem of finding a fixpoint of a c…
Approximating the Existential Theory of the Reals
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos +1
The Existential Theory of the Reals (ETR) consists of existentially quantified Boolean formulas over equalities and inequalities of polynomial functions of variables in $\mathbb{R}…
End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta +1
We introduce the problem EndOfPotentialLine and the corresponding complexity class EOPL of all problems that can be reduced to it in polynomial time. This class captures problems t…
CLS: New Problems and Completeness
John Fearnley, Spencer Gordon, Ruta Mehta +1
The complexity class CLS was introduced by Daskalakis and Papadimitriou with the goal of capturing the complexity of some well-known problems in PPADPLS that have resisted,…