= Superpolynomial monotone clique lower bound
{title2=$\operatorname{size}(\operatorname{CLIQUE}_{n,\lfloor n^{1/4}\rfloor})\geq\exp(c(\log n)^2)$}
In the <finite lattice approximation for monotone clique circuits>, set $m=r=\lfloor n^{1/4}\rfloor$ and $\ell=\lfloor\log_2n\rfloor$. A nonuniversal output accepts at most $\sum_{s=2}^\ell s!(r-1)^s(m/n)^s\leq2(\ell rm/n)^2$ of uniform positive <cliques>. Its missing positives require the circuit size times the <positive clique error of a truncated lattice meet> to be bounded below. A universal output accepts every negative colouring input; those errors require the circuit size times the <negative colouring error of a forced-set closure> to be at least one. Both alternatives imply the displayed superpolynomial bound by the <Razborov gate-by-gate approximation lemma>.
Back to article page
