In the finite lattice approximation for monotone clique circuits, set and . A nonuniversal output accepts at most 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.
Articles by others on the same topic
There are currently no matching articles.