2019/03/07 by Argyrios Deligkas, Deligkas, Argyrios, John Fearnley +5 · 1 citation
Computer Science · Decision Sciences · #Advanced Algebra and Logic #Algebraic Topology (math.AT) #Auction Theory and Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.1903.03101
openalex publication_date 2019/03/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of finding an exact solution to the consensus halving\nproblem. While recent work has shown that the approximate version of this\nproblem is PPA-complete, we show that the exact version is much harder.\nSpecifically, finding a solution with n cuts is FIXP-hard, and deciding\nwhether there exists a solution with fewer than n cuts is ETR-complete. We\nalso give a QPTAS for the case where each agent's valuation is a polynomial.\nAlong the way, we define a new complexity class BU, which captures all problems\nthat can be reduced to solving an instance of the Borsuk-Ulam problem exactly.\nWe show that FIXP \⊆ BU \⊆ TFETR and that LinearBU = PPA,\nwhere LinearBU is the subclass of BU in which the Borsuk-Ulam instance is\nspecified by a linear arithmetic circuit.\n