5 citations · 5 across the 2 of their papers we have counts for
4 papers
PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization
Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh +1
We introduce a general technique for proving membership of search problems with exact rational solutions in PPAD, one of the most well-known classes containing total search problem…
The Frontier of Intractability for EFX with Two Agents
Paul W. Goldberg, Kasper Høgh, Alexandros Hollender
We consider the problem of sharing a set of indivisible goods among agents in a fair manner, namely such that the allocation is envy-free up to any good (EFX). We focus on the prob…
FIXP-membership via Convex Optimization: Games, Cakes, and Markets
Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh +1
We introduce a new technique for proving membership of problems in FIXP - the class capturing the complexity of computing a fixed-point of an algebraic circuit. Our technique const…
Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem
Eleni Batziou, Kristoffer Arnsfelt Hansen, Kasper Høgh
In the consensus halving problem we are given n agents with valuations over the interval . The goal is to divide the interval into at most pieces (by placing at most n…