Consensus Halving Is PPA-Complete

Filos-Ratsikas, Aris ORCID: 0000-0001-7868-8114 and Goldberg, Paul W
(2018) Consensus Halving Is PPA-Complete. In: STOC '18: Symposium on Theory of Computing, Los Angeles, CA, USa.

[img] Text
1711.04503v1.pdf - Submitted Version

Download (506kB) | Preview


We show that the computational problem Consensus Halving is PPA-Complete, the first PPA-Completeness result for a problem whose definition does not involve an explicit circuit. We also show that an approximate version of this problem is polynomial-time equivalent to Necklace Splitting, which establishes PPAD-hardness for Necklace Splitting and suggests that it is also PPA-Complete.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: PPA-Completeness, Consensus-Halving, Necklace Splitting
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 24 Jun 2021 10:19
Last Modified: 06 Oct 2021 07:10
DOI: 10.1145/3188745.3188880
Related URLs: