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)}$.