On the black-box complexity of Sperner's Lemma
| dc.creator | Friedl, Katalin | |
| dc.creator | Ivanyos, Gabor | |
| dc.creator | Santha, Miklos | |
| dc.creator | Verhoeven, Yves F. | |
| dc.date | 2005-05-24 | |
| dc.date.accessioned | 2026-07-07T06:12:50Z | |
| dc.date.available | 2026-07-07T06:12:50Z | |
| dc.description | We present several results on the complexity of various forms of Sperner's Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an $O(\sqrt{n})$ deterministic query algorithm for the black-box version of the problem {\bf 2D-SPERNER}, a well studied member of Papadimitriou's complexity class PPAD. This upper bound matches the $Ω(\sqrt{n})$ deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an $Ω(\sqrt[4]{n})$ lower bound for its probabilistic, and an $Ω(\sqrt[8]{n})$ lower bound for its quantum query complexity, showing that all these measures are polynomially related. | |
| dc.description | 16 pages with 1 figure | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0505185 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0505185 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/92909 | |
| dc.subject | Quantum Physics | |
| dc.title | On the black-box complexity of Sperner's Lemma | |
| dc.type | text |