Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
From MaRDI portal
Publication:5092341
DOI10.4230/LIPIcs.ICALP.2019.138zbMath1498.68120OpenAlexW2966442265MaRDI QIDQ5092341
Argyrios Deligkas, Themistoklis Melissourgos, John Fearnley, Paul G. Spirakis
Publication date: 21 July 2022
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10714/pdf/LIPIcs-ICALP-2019-138.pdf/
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
Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ Approximating the existential theory of the reals
Cites Work
- Unnamed Item
- Unnamed Item
- Recognition and complexity of point visibility graphs
- Fixed points, Nash equilibria, and the existential theory of the reals
- 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
- Bidding for envy-freeness: a procedural approach to \(n\)-player fair-division problems
- 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
- 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
- The Complexity of Decision Problems about Nash Equilibria in Win-Lose Games
- 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
- Approximating the existential theory of the reals
