Timeline for Sperner's lemma and Tucker's lemma
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 3, 2020 at 17:29 | comment | added | François G. Dorais | @domotorp this is old, but it seems your comment should be an answer. | |
| Jul 31, 2017 at 7:59 | comment | added | domotorp | It turned out that Tucker was erroneously claimed to be in PPAD, it is PPA-complete, see [here][1]. This means that Tucker cannot be derived from Sperner, as these classes can be separated by an orcale, see [here][2]. As I wrote earlier, Sperner can be derived from Tucker. [1]: eccc.weizmann.ac.il/report/2015/163 [2]: doi.org/10.1016/0168-0072(96)83747-X | |
| Jun 13, 2013 at 20:22 | vote | accept | CommunityBot | ||
| Jun 13, 2013 at 20:22 | history | bounty ended | James Propp | ||
| Jun 7, 2013 at 10:10 | comment | added | domotorp | Both Borsuk-Ulam and Tucker have been studied and shown to be PPAD-complete in the linked paper. I also believe that this shows that Sperner can be derived from Tucker, however, it would be nice to have a simple, straightforward reduction. | |
| Jun 7, 2013 at 8:42 | comment | added | Rabee Tourky | Indeed, I don't think that Tucker has been studied in the context of PPAD complexity. It has been of some interest to me if Borsuk-Ulam is part of this class of path following proofs that Papadimitriou introduced. | |
| Jun 7, 2013 at 0:56 | history | answered | Andreas Blass | CC BY-SA 3.0 |