BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

John Fearnley

John Fearnley contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational ComplexityComputer Science and Game TheoryFormal Languages and Automata TheoryComputational GeometryData Structures and AlgorithmsLogic in Computer Sciencemath.ATmath.GN

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
8topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2021arXiv

Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem

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 show that the exact version is much harder. Specifically, finding a solution with $n$ cuts is FIXP-hard, and deciding whether there exists a solution with fewer than $n$ cuts is ETR-complete. We also give a QPTAS for the case where each agent's valuation is a polynomial. Along the way, we define a new complexity class BU, which captures all problems that can be reduced to solving an instance of the Borsuk-Ulam problem exactly. We show that FIXP $\subseteq$ BU $\subseteq$ TFETR and that LinearBU $=$ PPA, where LinearBU is the subclass of BU in which the Borsuk-Ulam instance is specified by a linear arithmetic circuit.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Approximating the Existential Theory of the Reals

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}$. In this paper we propose and study the approximate existential theory of the reals ($ε$-ETR), in which the constraints only need to be satisfied approximately. We first show that when the domain of the variables is $\mathbb{R}$ then $ε$-ETR = ETR under polynomial time reductions, and then study the constrained $ε$-ETR problem when the variables are constrained to lie in a given bounded convex set. Our main theorem is a sampling theorem, similar to those that have been proved for approximate equilibria in normal form games. It discretizes the domain in a grid-like manner whose density depends on various properties of the formula. A consequence of our theorem is that we obtain a quasi-polynomial time approximation scheme (QPTAS) for a fragment of constrained $ε$-ETR. We use our theorem to create several new PTAS and QPTAS algorithms for problems from a variety of fields.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

One-Clock Priced Timed Games are PSPACE-hard

The main result of this paper is that computing the value of a one-clock priced timed game (OCPTG) is PSPACE-hard. Along the way, we provide a family of OCPTGs that have an exponential number of event points. Both results hold even in very restricted classes of games such as DAGs with treewidth three. Finally, we provide a number of positive results, including polynomial-time algorithms for even more restricted classes of OCPTGs such as trees.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Tree Polymatrix Games are PPAD-hard

We prove that it is PPAD-hard to compute a Nash equilibrium in a tree polymatrix game with twenty actions per player. This is the first PPAD hardness result for a game with a constant number of actions per player where the interaction graph is acyclic. Along the way we show PPAD-hardness for finding an $ε$-fixed point of a 2D LinearFIXP instance, when $ε$ is any constant less than $(\sqrt{2} - 1)/2 \approx 0.2071$. This lifts the hardness regime from polynomially small approximations in $k$-dimensions to constant approximations in two-dimensions, and our constant is substantial when compared to the trivial upper bound of $0.5$.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Linear Complementarity Algorithms for Infinite Games

The performance of two pivoting algorithms, due to Lemke and Cottle and Dantzig, is studied on linear complementarity problems (LCPs) that arise from infinite games, such as parity, average-reward, and discounted games. The algorithms have not been previously studied in the context of infinite games, and they offer alternatives to the classical strategy-improvement algorithms. The two algorithms are described purely in terms of discounted games, thus bypassing the reduction from the games to LCPs, and hence facilitating a better understanding of the algorithms when applied to games. A family of parity games is given, on which both algorithms run in exponential time, indicating that in the worst case they perform no better for parity, average-reward, or discounted games than they do for general P-matrix LCPs.

0 citations0 reviewsNo code linkedOpen access