Consensus halving is PPA-complete

DOI10.1145/3188745.3188880MaRDI QIDQ5230276zbMATH OpenOpenAlexWikidataFDO

Authors 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

consensus-halvingnecklace splittingPPA-completeness

Mathematics Subject Classification ID

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

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.

Recommendations

• The complexity of splitting necklaces and bisecting ham sandwiches
• Hardness results for consensus-halving
• Consensus Halving for Sets of Items
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem

Cited in

(38)

• Towards a unified complexity theory of total functions
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• 2-D Tucker is PPA complete
• The complexity of the parity argument with potential
• The complexity of finding fair independent sets in cycles
• Two's company, three's a crowd: consensus-halving for a constant number of agents
• Almost envy-freeness for groups: improved bounds via discrepancy theory
• Understanding PPA-completeness
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• The Hairy Ball problem is PPAD-complete
• Consensus halving for sets of items
• Hardness results for consensus-halving
• The Hairy Ball Problem is PPAD-Complete.
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• scientific article; zbMATH DE number 7561747 (Why is no real title available?)
• Contiguous cake cutting: hardness results and approximation algorithms
• The complexity of splitting necklaces and bisecting ham sandwiches
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• Consensus Halving for Sets of Items
• scientific article; zbMATH DE number 7662165 (Why is no real title available?)
• Consensus-Halving: Does It Ever Get Easier?
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• Constant inapproximability for PPA
• Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
• Note on constrained long choice with multiple beginning elements
• The chromatic number of Kneser hypergraphs via consensus division
• Pizza sharing is PPA-hard
• A fixed-parameter algorithm for the Schrijver problem
• On the complexity of some restricted variants of \textsc{Quotient Pigeon} and a weak variant of \textsc{Kőnig}
• Ordinal maximin guarantees for group fair division
• Constant inapproximability for PPA
• The complexity of finding fair independent sets in cycles
• Total functions in the polynomial hierarchy
• Efficient splitting of necklaces
• Strong approximate consensus halving and the Borsuk-Ulam theorem
• Settling the complexity of Nash equilibrium in congestion games

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230276)