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

Abstract

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: 18 Jan 2023 21:37
DOI: 10.1145/3188745.3188880
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3127558