Computing exact solutions of consensus halving and the Borsuk-Ulam theorem

DOI10.1016/j.jcss.2020.10.006zbMath1477.68115arXiv1903.03101OpenAlexW3101401168MaRDI QIDQ2221804

Themistoklis Melissourgos, John Fearnley, Argyrios Deligkas, Paul G. Spirakis

Publication date: 2 February 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

reductioncircuitcomplexity classPPAconsensus halvingETRFIXP

Mathematics Subject Classification ID

Fixed points and coincidences in algebraic topology (55M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ Consensus-Halving: Does It Ever Get Easier? ⋮ Almost envy-freeness for groups: improved bounds via discrepancy theory ⋮ Unnamed Item ⋮ Approximating the existential theory of the reals ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on square roots of nonnegative matrices
• Recognition and complexity of point visibility graphs
• Splitting necklaces
• Some provably hard crossing number problems
• On the complexity of the parity argument and other inefficient proofs of existence
• A Sperner lemma complete for PPA
• Max-min representation of piecewise linear functions
• An improved envy-free cake cutting protocol for four agents
• Complexity of rational and irrational Nash equilibria
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• 2-D Tucker is PPA complete
• Bidding for envy-freeness: a procedural approach to \(n\)-player fair-division problems
• Generalized sandwich theorems
• Rental Harmony: Sperner's Lemma in Fair Division
• Realizability of Graphs and Linkages
• On the Complexity of Nash Equilibria and Other Fixed Points
• Who Needs Crossings? Hardness of Plane Graph Rigidity
• Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
• ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
• Settling the complexity of computing two-player Nash equilibria
• Complexity of Some Geometric and Topological Problems
• Inapproximability of Nash Equilibrium
• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games
• An Envy-Free Cake Division Protocol
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• The Complexity of Decision Problems about Nash Equilibria in Win-Lose Games
• Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
• The complexity of splitting necklaces and bisecting ham sandwiches
• Consensus halving is PPA-complete
• The art gallery problem is ∃ ℝ-complete
• Constant rank bimatrix games are PPAD-hard
• The Complexity of Positive Semidefinite Matrix Factorization
• A discrete and bounded envy-free cake cutting protocol for four agents
• Understanding PPA-completeness
• Near-Optimal Separators in String Graphs
• Rank-1 bimatrix games
• On the computational complexity of decision problems about multi-player Nash equilibria

This page was built for publication: Computing exact solutions of consensus halving and the Borsuk-Ulam theorem