@inproceedings{149b0130bf8641108d17bb62f4c5cb68,
title = "Hardness results for consensus-halving",
abstract = "The Consensus-halving problem is the problem of dividing an object into two portions, such that each of n agents has equal valuation for the two portions. We study the -approximate version, which allows each agent to have an discrepancy on the values of the portions. It was recently proven in [13] that the problem of computing an -approximate Consensus-halving solution (for n agents and n cuts) is PPA-complete when is inverse-exponential. In this paper, we prove that when is constant, the problem is PPAD-hard and the problem remains PPAD-hard when we allow a constant number of additional cuts. Additionally, we prove that deciding whether a solution with n − 1 cuts exists for the problem is NP-hard.",
keywords = "Consensus halving, Generalized-circuit, PPA, PPAD, Reduction",
author = "Aris Filos-Ratsikas and \{Stiil Frederiksen\}, \{S{\o}ren Kristoffer\} and Goldberg, \{Paul W.\} and Jie Zhang",
year = "2018",
month = aug,
day = "1",
doi = "10.4230/LIPIcs.MFCS.2018.24",
language = "English",
isbn = "9783959770866",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Igor Potapov and James Worrell and Paul Spirakis",
booktitle = "43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018",
address = "Germany",
note = "43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 ; Conference date: 27-08-2018 Through 31-08-2018",
}
