
SquareCut Pizza Sharing is PPAcomplete
We study the computational complexity of computing solutions for the squ...
read it

The Complexity of Gradient Descent: CLS = PPAD ∩ PLS
We study search problems that can be solved by performing Gradient Desce...
read it

A faster algorithm for finding Tarski fixed points
Dang et al. have given an algorithm that can find a Tarski fixed point i...
read it

Tree Polymatrix Games are PPADhard
We prove that it is PPADhard to compute a Nash equilibrium in a tree po...
read it

OneClock Priced Timed Games are PSPACEhard
The main result of this paper is that computing the value of a oneclock...
read it

Computing Exact Solutions of Consensus Halving and the BorsukUlam Theorem
We study the problem of finding an exact solution to the consensus halvi...
read it

Unique End of Potential Line
This paper studies the complexity of problems in PPAD ∩ PLS that have un...
read it

Approximating the Existential Theory of the Reals
The existential theory of the reals (ETR) consists of existentially quan...
read it

An Improved EnvyFree Cake Cutting Protocol for Four Agents
We consider the classic cakecutting problem of producing envyfree allo...
read it

Market Making via Reinforcement Learning
Market making is a fundamental trading problem in which an agent provide...
read it

End of Potential Line
We introduce the problem EndOfPotentialLine and the corresponding comple...
read it

Reachability Switching Games
In this paper, we study the problem of deciding the winner of reachabili...
read it
John Fearnley
is this you? claim profile