<a href="index.html"> Discrete Math/Theory of Computing seminar </a> January 23, 2001

Regular Resolution Lower Bounds for the Weak Pigeonhole Principle

Ran Raz, Weizmann Institute and Institute for Advanced Study

January 23, 4:30 PM, Rutgers Univ. CORE building, Room 431

Abstract.

We prove that any regular resolution proof for the weak pigeonhole principle with n holdes and any number of pigeons is of length Omega(2^{n^a}) for some global constant a>0.

This is joint work with Toni Pitassi.

Back to Discrete Math/Theory of Computing seminar