Hardness results for consensus-halving

DOI10.4230/LIPICS.MFCS.2018.24MaRDI QIDQ5005124zbMATH OpenFDO

Authors Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang

Publication date 4 August 2021

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

zbMATH Keywords

consensus-halvinggeneralized circuitPPAPPADreduction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

• Consensus halving is PPA-complete
• 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
• Consensus-halving via theorems of Borsuk-Ulam and Tucker

Cites work

• 2-D Tucker is PPA complete
• A constructive proof of Ky Fan's generalization of Tucker's lemma
• A Moment Problem in L 1 Approximation
• Bidding for envy-freeness: a procedural approach to \(n\)-player fair-division problems
• Bisection of Circle Colorings
• Consensus halving is PPA-complete
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• Drei Sätze über die n-dimensionale euklidische Sphäre
• Elementary inequalities between the expected values of current estimates of variance
• Four-Person Envy-Free Chore Division
• scientific article; zbMATH DE number 48315 (Why is no real title available?)
• scientific article; zbMATH DE number 1234106 (Why is no real title available?)
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• scientific article; zbMATH DE number 3097423 (Why is no real title available?)
• scientific article; zbMATH DE number 3102257 (Why is no real title available?)
• Inapproximability of Nash equilibrium
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Rental Harmony: Sperner's Lemma in Fair Division
• Settling the complexity of computing two-player Nash equilibria
• Simplicial maps from an orientable n-pseudomanifold into Sm with the octahedral triangulation
• Splitting necklaces
• Super envy-free cake division and independence of measures
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• The complexity of computing a Nash equilibrium
• The complexity of non-monotone markets
• The complexity of splitting necklaces and bisecting ham sandwiches

Cited in

(19)

• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• On the effective block size in Harper's theorem
• 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
• Consensus halving for sets of items
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Consensus halving is PPA-complete
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• Consensus Halving for Sets of Items
• Consensus-Halving: Does It Ever Get Easier?
• Constant inapproximability for PPA
• Pizza sharing is PPA-hard
• Pure-circuit: tight inapproximability for PPAD
• Constant inapproximability for PPA
• The complexity of finding fair independent sets in cycles
• Efficient splitting of necklaces
• Strong approximate consensus halving and the Borsuk-Ulam theorem

This page was built for publication: Hardness results for consensus-halving

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