Title: A switching lemma for mall restrictions and lower bounds for k-DNF Resolution
Speaker: Russell Impagliazzo, University of California at San Diego
Date: September 10, 4:30 PM
Location: Rutgers Univ. CORE 431
We prove a new switching lemma that works for restrictions that set only a small fraction of the variables and is applicable to DNFs with small bottom fan-in. We use this to prove lower bounds for the Res(k) propositional proof system, an extension of resolution whose lines are k-DNFs instead of clauses. We also obtain an exponential separation between depth d circuits of bottom fan-in k and depth d circuits of bottom fan-in k+1.
Our results for Res(k) proofs are:
In principle this talk will be self-contained; I will review needed definitions concerning boolean formulas and resolution.