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 formulas in disjunctive normal form (DNFs) with small terms. 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 as follows: The 2n to n weak pigeonhole principle requires exponential size to refute in Res(k) 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 Res(k). 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 |
|---|---|---|
2004 | 10.1137/S0097539703428555 | foundations of computer science |
Keywords | Field | DocType |
random restriction,resolution,polynomial size Res,switching lemmas,Small Restrictions,circuit bottom fan-in,constant w k,constant k,k-dnfs,exponential size,small fraction,bottom fan-in k,resk,weak pigeonhole principles,exponential separation,k-DNF Resolution,propositional proof complexity,lower bounds,sipser functions,exponential size Res,log n,Switching Lemma,random cnfs,small term,Lower Bounds,boolean circuit complexity | Log-log plot,Binary logarithm,Discrete mathematics,Combinatorics,Exponential function,Polynomial,Propositional proof system,Mathematics,Lemma (mathematics),Pigeonhole principle,Computational complexity theory | Journal |
Volume | Issue | ISSN |
33 | 5 | 0097-5397 |
Citations | PageRank | References |
34 | 1.17 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nathan Segerlind | 1 | 223 | 11.22 |
| Sam Buss | 2 | 122 | 11.58 |
| Russell Impagliazzo | 3 | 5444 | 482.13 |