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:

  1. The  2n  to  n  weak pigeonhole principle requires exponential size to refute in $\Resk$, for $k \leq \sqrt{\log n / \log \log n } $
  2. For each constant  k, there exists a constant $w>k$ so that random $w$-CNFs require exponential size to refute in ${\mbox{Res}}(k)$.
  3. 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

Back to Sam Buss's publications page.