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

Deligkas, Argyrios, Fearnley, John, Melissourgos, Themistoklis ORCID: 0000-0002-9867-6257 and Spirakis, Paul G
(2019) Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem.

This is the latest version of this item.

[img] Text
LIPIcs-ICALP-2019-138.pdf - OA Published Version

Download (686kB) | Preview


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.

Item Type: Article
Uncontrolled Keywords: cs.CC, cs.CC, math.AT
Depositing User: Symplectic Admin
Date Deposited: 30 Jan 2020 14:08
Last Modified: 29 Apr 2022 11:54
Open Access URL:
Related URLs:

Available Versions of this Item