Result: On the black-box complexity of Sperner's Lemma

Title:
On the black-box complexity of Sperner's Lemma
Authors:
FRIEDL, Katalin, IVANYOS, Gabor, SANTHA, Miklos, VERHOEVEN, Yves F
Source:
FCT 2005 : fundamentals of computationals theory (Lübeck, 17-20 August 2005)Lecture notes in computer science. :245-257
Publisher Information:
Berlin: Springer, 2005.
Publication Year:
2005
Physical Description:
print, 26 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithme déterministe, Deterministic algorithms, Analyse fonctionnelle, Functional analysis, Análisis funcional, Approche déterministe, Deterministic approach, Enfoque determinista, Approche probabiliste, Probabilistic approach, Enfoque probabilista, Borne inférieure, Lower bound, Cota inferior, Borne supérieure, Upper bound, Cota superior, Classe complexité, Complexity class, Clase complejidad, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Informatique théorique, Computer theory, Informática teórica, Interrogation base donnée, Database query, Interrogación base datos, Modélisation, Modeling, Modelización, Squelette, Skeleton, Esqueleto
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
BUTE, P.O.Box 91, 1521 Budapest, Hungary
MTA SZTAKI, P.O. Box 91, 1518 Budapest, Hungary
CNRS-LRI, UMR 8623, Université Paris XI, 91405 Orsay, France
ENST, 46 rue Barrault, 75013 Paris, France
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=17115875
Rights:
Copyright 2005 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.17115875
Database:
PASCAL Archive

Further Information

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(n) deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou's complexity class PPAD. This upper bound matches the Ω(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 Ω(4n) lower bound for its probabilistic, and an Ω(8n) lower bound for its quantum query complexity, showing that all these measures are polynomially related.