Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
On the complexity of the Sperner Lemma

Speaker: Stefan Dantchev
Presentation: main.pdf
Slot: Tue, 10:30-10:50, Faraday B (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 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net