The Hairy Ball problem is PPAD-complete

DOI10.1016/J.JCSS.2021.05.004OpenAlexW2965985967WikidataQ113398676 ScholiaQ113398676MaRDI QIDQ2229948FDOQ2229948

Authors: Paul W. Goldberg, Alexandros Hollender 

Publication date: 17 September 2021

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

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

Recommendations

• The Hairy Ball Problem is PPAD-Complete.
• On the complexity of 2D discrete fixed point problem
• A Sperner lemma complete for PPA
• \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma
• On the Complexity of 2D Discrete Fixed Point Problem

zbMATH Keywords

computational complexityPPADTFNPend-of-line

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Title not available (Why is that?)
• The complexity of computing a Nash equilibrium
• The computation of fixed points and applications
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of the parity argument and other inefficient proofs of existence
• Analytic Proofs of the "Hairy Ball Theorem" and the Brouwer Fixed Point Theorem
• Settling the complexity of computing two-player Nash equilibria
• On total functions, existence theorems and computational complexity
• The relative complexity of NP search problems
• Propositional proofs and reductions between NP search problems
• A Proof of the Hairy Ball Theorem
• Title not available (Why is that?)
• Algorithmic solutions for envy-free cake cutting
• A converse to Banach's fixed point theorem and its CLS-completeness
• On the complexity of 2D discrete fixed point problem
• Towards a unified complexity theory of total functions
• Inapproximability of Nash equilibrium
• Reducibility among fractional stability problems
• Consensus halving is PPA-complete
• 2-D Tucker is PPA complete
• The complexity of splitting necklaces and bisecting ham sandwiches
• Another short proof of the hairy ball theorem
• The Hairy Ball Theorem via Sperner's Lemma
• An Extremely Short Proof of the Hairy Ball Theorem
• On Two Classical Theorems of Algebraic Topology

Cited In (9)

• On the Complexity of Equilibrium Computation in First-Price Auctions
• The complexity of gradient descent: CLS = PPAD \(\cap\) pls
• Discrete versions of the KKM lemma and their PPAD-completeness
• Financial networks with singleton liability priorities
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• Consensus-Halving: Does It Ever Get Easier?
• Financial networks with singleton liability priorities
• The complexity of finding fair independent sets in cycles
• Further collapses in \(\mathsf{TFNP}\)

This page was built for publication: The Hairy Ball problem is PPAD-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2229948)