Understanding PPA-completeness
DOI10.1016/j.jcss.2020.07.006zbMath1464.68121OpenAlexW3047060986MaRDI QIDQ2208253
Jack Edmonds, Zhe Feng, Xiaotie Deng, Zeying Xu, Qi Qi, Zhengyang Liu
Publication date: 23 October 2020
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5831/
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Triangulating manifolds (57Q15) Relations of low-dimensional topology with graph theory (57M15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exponential lower bounds for finding Brouwer fixed points
- On the complexity of 2D discrete fixed point problem
- The computation of fixed points and applications
- Some graphic uses of an even number of odd nodes
- The complexity of finding a second Hamiltonian cycle in cubic graphs
- On the complexity of the parity argument and other inefficient proofs of existence
- A Sperner lemma complete for PPA
- Complementary pivot theory of mathematical programming
- Discrete Fixed Points: Models, Complexities, and Applications
- Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
- Settling the complexity of computing two-player Nash equilibria
- Matching algorithmic bounds for finding a Brouwer fixed point
- The complexity of promise problems with applications to public-key cryptography
- Some Combinatorial Lemmas in Topology
- Hamiltonian Cycles and Uniquely Edge Colourable Graphs
- Combinatorial Nullstellensatz
- Consensus halving is PPA-complete
- Constant rank bimatrix games are PPAD-hard
- Equilibrium Points of Bimatrix Games
- Hard-to-Solve Bimatrix Games
- The Approximation of Fixed Points of a Continuous Mapping
- Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs
This page was built for publication: Understanding PPA-completeness