On the black-box complexity of Sperner's Lemma

Katalin Friedl, Gabor Ivanyos, Miklos Santha +1

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 ps…