Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
On the complexity of the Sperner Lemma

Speaker: Stefan Dantchev
Slot: Array, 10:30-10:50, col. 2


We show a reduction from the Pigeon-Hole Principle to the
classical Sperner Lemma. We use the reduction to
1. prove that the Sperner Lemma is hard for Constant-Depth Frege, and
2. prove a query complexity lower bound for the Sperner Lemma in
the black-box settings. 

websites: Arnold Beckmann 2006-04-19