Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-068 | 27th April 2019 01:40

LARGE CLIQUE IS HARD ON AVERAGE FOR RESOLUTION

RSS-Feed




TR19-068
Authors: Shuo Pang
Publication: 9th May 2019 19:39
Downloads: 140
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint