27 citations · 187 across the 36 of their papers we have counts for
5 papers · 1 filter
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}…
An Improved Envy-Free Cake Cutting Protocol for Four Agents
Georgios Amanatidis, George Christodoulou, John Fearnley +3
We consider the classic cake-cutting problem of producing envy-free allocations, restricted to the case of four agents. The problem asks for a partition of the cake to four agents,…
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…
Market Making via Reinforcement Learning
Thomas Spooner, John Fearnley, Rahul Savani +1
Market making is a fundamental trading problem in which an agent provides liquidity by continually offering to buy and sell a security. The problem is challenging due to inventory…