Computability in Europe 2006
Logical Approaches to Computational Barriers
|Slot:||Tue, 10:30-10:50, Faraday B (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|