dorsal/arxiv
View SchemaOn the black-box complexity of Sperner's Lemma
| Authors | Katalin Friedl, Gabor Ivanyos, Miklos Santha, Yves F. Verhoeven |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0505185 |
| URL | https://arxiv.org/abs/quant-ph/0505185 |
Abstract
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 $\Omega(\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 $\Omega(\sqrt[4]{n})$ lower bound for its probabilistic, and an $\Omega(\sqrt[8]{n})$ lower bound for its quantum query complexity, showing that all these measures are polynomially related.
{
"annotation_id": "8ed9c3de-3b9a-4184-8cd9-b26a5f5626c4",
"date_created": "2026-03-02T18:02:16.984000Z",
"date_modified": "2026-03-02T18:02:16.984000Z",
"file_hash": "842e59e913c68eeb47543aae7ecb8c4d2626549dfddfbd333cb0e5abf2257002",
"private": false,
"record": {
"abstract": "We present several results on the complexity of various forms of Sperner\u0027s\nLemma in the black-box model of computing. We give a deterministic algorithm\nfor Sperner problems over pseudo-manifolds of arbitrary dimension. The query\ncomplexity of our algorithm is linear in the separation number of the skeleton\ngraph of the manifold and the size of its boundary. As a corollary we get an\n$O(\\sqrt{n})$ deterministic query algorithm for the black-box version of the\nproblem {\\bf 2D-SPERNER}, a well studied member of Papadimitriou\u0027s complexity\nclass PPAD. This upper bound matches the $\\Omega(\\sqrt{n})$ deterministic lower\nbound of Crescenzi and Silvestri. The tightness of this bound was not known\nbefore. In another result we prove for the same problem an\n$\\Omega(\\sqrt[4]{n})$ lower bound for its probabilistic, and an\n$\\Omega(\\sqrt[8]{n})$ lower bound for its quantum query complexity, showing\nthat all these measures are polynomially related.",
"arxiv_id": "quant-ph/0505185",
"authors": [
"Katalin Friedl",
"Gabor Ivanyos",
"Miklos Santha",
"Yves F. Verhoeven"
],
"categories": [
"quant-ph"
],
"title": "On the black-box complexity of Sperner\u0027s Lemma",
"url": "https://arxiv.org/abs/quant-ph/0505185"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "f220ebce-1812-416f-a746-383b45c42c9e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}