We prove an \exp({\Omega(k^{(1-\epsilon)})}) resolution size lower bound for the k-Clique problem on random graphs, for (roughly speaking) k<n^{1/3}. Towards an optimal resolution lower bound of the problem (i.e. of type n^{\Omega(k)}), we also extend the n^{\Omega(k)} bound in \cite{ABDLNR17} on regular resolution to a stronger model called {\it a-irregular resolution}, for k<n^{1/3}. This model is interesting in that all known CNF families separating regular resolution from general \cite{alekhnovich2002exponential,vinyals2020simplified} have short proofs in it.

Improved presentation.

We prove resolution lower bounds for k-Clique on the Erdos-Renyi random graph G(n,n^{-{2\xi}\over{k-1}}) (where \xi>1 is constant). First we show for k=n^{c_0}, c_0\in(0,1/3), an \exp({\Omega(n^{(1-\epsilon)c_0})}) average lower bound on resolution where \epsilon 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^{\Omega(k)} average lower bound of k-Clique for this model, for {\it any} k<n^{1/3-\Omega(1)}.