Consensus halving is PPA-complete

DOI10.1145/3188745.3188880zbMath1428.68162arXiv1711.04503OpenAlexW2963086090MaRDI QIDQ5230276

Aris Filos-Ratsikas, Paul W. Goldberg

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.04503

zbMATH Keywords

necklace splittingconsensus-halvingPPA-completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (22)

Consensus-Halving: Does It Ever Get Easier? ⋮ Almost envy-freeness for groups: improved bounds via discrepancy theory ⋮ Fixed-Parameter Algorithms for the Kneser and Schrijver Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Understanding PPA-completeness ⋮ Contiguous Cake Cutting: Hardness Results and Approximation Algorithms ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ The Hairy Ball problem is PPAD-complete ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ Towards a unified complexity theory of total functions ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ 2-D Tucker is PPA complete ⋮ Unnamed Item ⋮ The complexity of the parity argument with potential ⋮ The Hairy Ball Problem is PPAD-Complete. ⋮ Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ The complexity of finding fair independent sets in cycles ⋮ Two's company, three's a crowd: consensus-halving for a constant number of agents ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich ⋮ Consensus Halving for Sets of Items

This page was built for publication: Consensus halving is PPA-complete