Finite lattice approximation for monotone clique circuits
ID: finite-lattice-approximation-for-monotone-clique-circuits
Take upward-closed set families of subsets of of size at most , closed under the forcing rule in Razborov closure. Normalize any family containing a set of size at most one to the full family, since its clique predicate is identically true. Intersection is the meet in a lattice; closure of the union is the join in a lattice. A family represents the graphs containing a clique on at least one of its members. The approximate meet can lose positive inputs and the approximate join can acquire negative inputs. The Razborov gate-by-gate approximation lemma charges output errors to those local errors.
New to topics? Read the docs here!