The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
From MaRDI portal
Publication:5863324
DOI10.1137/20M1312678OpenAlexW4214564166MaRDI QIDQ5863324
Paul W. Goldberg, Aris Filos-Ratsikas
Publication date: 11 March 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1312678
Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- New approaches to multi-objective optimization
- Propositional proofs and reductions between NP search problems
- On total functions, existence theorems and computational complexity
- Integer factoring and modular square roots
- The complexity of equilibria: Hardness results for economies via a correspondence with games
- Paintshop, odd cycles and necklace splitting
- On the complexity of 2D discrete fixed point problem
- Computing a ham-sandwich cut in two dimensions
- Splitting necklaces
- How easy is local search?
- A constructive proof of Tucker's combinatorial lemma
- The relative complexity of NP search problems
- On the complexity of the parity argument and other inefficient proofs of existence
- Algorithms for ham-sandwich cuts
- A Sperner lemma complete for PPA
- Towards a unified complexity theory of total functions
- Computing solutions of the paintshop-necklace problem
- Consensus-halving via theorems of Borsuk-Ulam and Tucker
- 2-D Tucker is PPA complete
- Unique end of potential line
- Understanding PPA-completeness
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- The Hairy Ball problem is PPAD-complete
- Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
- Simplotopal maps and necklace splitting
- Complexity results on restricted instances of a paint shop problem for words
- The Borsuk--Ulam-property, Tucker-property and constructive proofs in combinatorics
- Generalized sandwich theorems
- Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
- On the Complexity of Nash Equilibria in Anonymous Games
- Market equilibrium under separable, piecewise-linear, concave utilities
- Discrete Splittings of the Necklace
- Bisection of Circle Colorings
- Determining a Fair Border
- On the impact of combinatorial structure on congestion games
- Settling the complexity of computing two-player Nash equilibria
- Constant Rank Two-Player Games are PPAD-hard
- Inapproximability of Nash Equilibrium
- Ham Sandwich is Equivalent to Borsuk-Ulam
- Thieves can make sandwiches
- The Borsuk-Ulam Theorem and Bisection of Necklaces
- Algorithmic Solutions for Envy-Free Cake Cutting
- Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
- Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
- The Complexity of Computing a Nash Equilibrium
- Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
- A converse to Banach's fixed point theorem and its CLS-completeness
- Consensus halving is PPA-complete
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- Reducibility among Fractional Stability Problems
- The complexity of non-monotone markets
- A Moment Problem in L 1 Approximation
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
- The complexity of gradient descent: CLS = PPAD ∩ PLS
This page was built for publication: The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
