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 ORCID: 0000-0001-5396-3749 (2019) Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. Leibniz International Proceedings in Informatics, LIPIcs, 132.

This is the latest version of this item.

Access the full-text of this item by clicking on the Open Access link.

Text
LIPIcs-ICALP-2019-138.pdf - Published version
Download (686kB) | Preview

Abstract

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:	19 Jan 2023 00:05
DOI:	10.4230/LIPIcs.ICALP.2019.138
Open Access URL:	https://arxiv.org/abs/1903.03101
Related URLs:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3072700