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

Abstract

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