scientific article; zbMATH DE number 7561747
From MaRDI portal
Publication:5092469
DOI10.4230/LIPIcs.CCC.2020.19MaRDI QIDQ5092469
Manolis Zampetakis, Mika Göös, Pritish Kamath, Katerina Sotiraki
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1912.04467
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (4)
Consensus-Halving: Does It Ever Get Easier? ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ 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
- Propositional proofs and reductions between NP search problems
- Regular subgraphs of almost regular graphs
- On total functions, existence theorems and computational complexity
- Integer factoring and modular square roots
- Splitting necklaces
- How easy is local search?
- The relative complexity of NP search problems
- On the complexity of the parity argument and other inefficient proofs of existence
- A Sperner lemma complete for PPA
- Bemerkung zur vorstehenden Arbeit von Herrn Chevalley
- 2-D Tucker is PPA complete
- On Kemnitz' conjecture concerning lattice-points in the plane
- Bisection of Circle Colorings
- On a Topological Generalization of a Theorem of Tverberg
- The Borsuk-Ulam Theorem and Bisection of Necklaces
- Adventures in monotone complexity and TFNP
- The Complexity of Computing a Nash Equilibrium
- The complexity of splitting necklaces and bisecting ham sandwiches
- Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
- White-Box vs. Black-Box Complexity of Search Problems
- Consensus halving is PPA-complete
- Sum-of-squares meets Nash: lower bounds for finding any equilibrium
- Understanding PPA-completeness
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- Counting classes: Thresholds, parity, mods, and fewness
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
This page was built for publication:
