Conference item
The Hairy Ball problem is PPAD-complete
- Abstract:
-
The Hairy Ball Theorem states that every continuous tangent vector field on an even-dimensional sphere must have a zero. We prove that the associated computational problem of computing an approximate zero is PPAD-complete. We also give a FIXP-hardness result for the general exact computation problem. In order to show that this problem lies in PPAD, we provide new results on multiple-source variants of End-of-Line, the canonical PPAD-complete problem. In particular, finding an approximate zero...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Version of record, pdf, 456.9KB)
-
- Publisher copy:
- 10.4230/LIPIcs.ICALP.2019.65
Authors
Funding
+ Engineering and Physical Sciences Research Council
More from this funder
Funding agency for:
Hollender, A
Grant:
1892947
Bibliographic Details
- Publisher:
- Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik Publisher's website
- Host title:
- 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
- Series:
- Leibniz International Proceedings in Informatics
- Journal:
- ICALP 2019 Journal website
- Volume:
- 132
- Pages:
- 65:1-65:14
- Publication date:
- 2019-07-08
- Acceptance date:
- 2019-04-19
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959771092
Item Description
- Keywords:
- Pubs id:
-
pubs:995291
- UUID:
-
uuid:a74e646f-3166-4648-aa52-153e0f5dadd0
- Local pid:
- pubs:995291
- Source identifiers:
-
995291
- Deposit date:
- 2019-05-01
Terms of use
- Copyright holder:
- Goldberg et al
- Copyright date:
- 2019
- Notes:
- © Paul W. Goldberg and Alexandros Hollender; licensed under Creative Commons License CC-BY. This conference paper was presented at the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record