LOWER BOUNDS FOR K-DNF RESOLUTION ON RANDOM 3-CNFS

We prove exponential lower bounds on refutations of a random 3-CNF with linear number of clauses by k-DNF Resolution for k <= root log n/log log n. For this we design a specially tailored random restrictions that preserve the structure of the input random 3-CNF while mapping every k-DNF with large covering number to one with high probability. Next we make use of the switching lemma for small restrictions by Segerlind, Buss and Impagliazzo to prove the lower bound. This work improves the previously known lower bound for Res(2) system on random 3-CNFs by Atserias, Bonet and Esteban and the result of Segerlind, Buss, Impagliazzo stating that random O(k(2))-CNF do not possess short Res(k)refutations.