We prove resolution lower bounds for k -Clique on the Erdos-Renyi random graph G ( n n − 2 k − 1 ) (where 1"> 1 is constant). First we show for k = n c 0 , c 0 ( 0 1 3) , an exp ( ( n (1 − ) c 0 ) ) average lower bound on resolution where is arbitrary constant.

We then propose the model of a -irregular resolution. Extended from regular resolution, this model is interesting in that the power of general-over-regular resolution from all {\it known} exponential separations is below it. We prove an n ( k ) average lower bound of k -Clique for this model, for {\it any} k n 1 3 − (1) .