Name
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 Res(k) 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 Res(k) are:1. The 2n to n weak pigeonhole principle requires exponential size to refute in Res(k), for k \leqslant \sqrt {{{\log n} \mathord{\left/ {\vphantom {{\log n} {\log \log n}}} \right. \kern-\nulldelimiterspace} {\log \log n}}}.2. For each constant k, there exists a constant wk so that random w -CNFs require exponential size to refute in 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 Res(k) refutations. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1137/S0097539703428555 | SIAM Journal on Computing |
Keywords | Field | DocType |
exponential size,bottom fan-in k,small fraction,small conjunction,exponential separation,polynomial size res,log n,exponential size res,small restrictions,switching lemma,dnf resolution,constant k,lower bounds,constant wk,boolean circuits,resolution,lower bound | Discrete mathematics,Binary logarithm,Combinatorics,Exponential function,Polynomial,Upper and lower bounds,Propositional proof system,Disjunctive normal form,Mathematics,Lemma (mathematics),Pigeonhole principle | Conference |
Volume | Issue | ISSN |
33 | 5 | 0097-5397 |
Citations | PageRank | References |
42 | 1.34 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nathan Segerlind | 1 | 223 | 11.22 |
| Samuel R. Buss | 2 | 956 | 84.19 |
| Russell Impagliazzo | 3 | 5444 | 482.13 |