A switching lemma for small restrictions and lower bounds for k-DNF resolution

Autor: Segerlind, Nate, Buss, Sam, Impagliazzo, Russell

Publikováno v: Segerlind, Nate; Buss, Sam; & Impagliazzo, Russell. (2004). A switching lemma for small restrictions and lower bounds for k-DNF resolution. SIAM Journal on Computing, 33(5), 1171-1200. UC San Diego: Retrieved from: http://www.escholarship.org/uc/item/5g36h6rk

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) propositiona

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=od_______325::e33fd3dcb94b9a260bd65efc68af9e31
http://www.escholarship.org/uc/item/5g36h6rk