__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:

- The
*2n*to*n*weak pigeonhole principle requires exponential size to refute in $\Resk$, for $k \leq \sqrt{\log n / \log \log n } $ - For each constant
*k*, there exists a constant $w>k$ so that random $w$-CNFs require exponential size to refute in ${\mbox{Res}}(k)$. - For each constant
*k*, there are sets of clauses which have polynomial size $\Res{k+1}$ refutations, but which require exponential size $\Resk$ refutations.

__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. **