Research article:
Nate Segerlind, Samuel R. Buss, and Russell Impagliazzo.
"A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF
Resolution."
SIAM Journal on Computing 33, no 5 (2004) 1171-1200 .
Download article: postscript or PDF.
Abstract: 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 conjunctions. We use this to prove lower bounds for the $\Resk$ propositional
proof system, an extension of resolution which works with 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 $\Resk$ are:
Earlier conference proceedings paper:
Nate Segerlind, Samuel R. Buss, and Russell Impagliazzo.
"A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF
Resolution (Extended Abstract)."
In: Proceedings of the 43rd Annual Symposium on
Foundations of Computer Science (FOCS'02),
IEEE Computer Society, 2002, pp 604-613.
Download conference proceedings article: postscript or PDF.