Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 124 / 2 / v / Solution

Let a monotone circuit of size $M$ compute the $m$-clique function, and let $\tilde{S}=⟨A⟩$ be its lattice approximation from part (i). If $\tilde{S}$ is not universal, part (ii) says that it misses at least half of all positive $m$-cliques. The approximation lemma and part (iii) then implyIf $\tilde{S}$ is universal, every complete $(m-1)$-partite graph is a negative input that must be covered by a union-error set. Part (iv) givesThereforeChoosewith constants satisfying the two hypotheses and $r>2l{\log }_{2}n$. Both lower bounds are thenSince the graph has $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ input variables, this is exponential in a positive power of the number of inputs, up to a logarithmic factor.