Exponential Lower Bounds for the Pigeonhole Principle

Paul Beame, Russell Impagliazzo, Jan Krajcek, Toniann Pitassi, Pavel Pudlk, Alan R. Woods

Browse the full STOC paper archive.