An Exponential Separation between the Matching Principle and the Pigeonhole Principle

Paul Beame, Toniann Pitassi

Browse the full LICS paper archive.