The Switching Lemma is a key result in proving lower bounds in circuit complexity. In this paper we approach the Switching Lemma from the standpoint of the semantics of the boolean function, i.e., its set of satisfying assignments. This novel approach, gives the exact bound probability when the boolean function is of a special form and may also lead to a simpler proof of the general case.
The rest of the paper is organized as follows. In the next section we give the necessary de nitions and notation. In Section 3 we give a novel formulation of the Switching Lemma in terms of binary vectors. In Section 4 we give the exact bound for a speci c case and outline a simpli ed proof of the general bound from the bibliography. We conclude with a list of references. 2
Let X = fx1; : : : ; xng be a set of Boolean variables. A literal is either a variable (called positive literal) or its negation (called negative literal). A clause is a disjunction of one or more literals such that each variable appears at most once, while a term is, analogously, a conjunction of literals. A Boolean expression may come in a variety of syntactic forms with more populars being the conjunctive normal form (CNF) and the disjunctive normal form (DNF). A CNF is a conjunction of clauses ' = C1 ^ C2 ^ ^ Cm, while a DNF is a disjunction of terms ' = T1 _ T2 _ _ Tt. In the rst relation each Ci; i = 1; :::; m is a clause, that is, Ci = `1 _ `2 _ _ `k, where each `j ; j = 1; : : : ; k is a literal. If every clause in ' is the conjunction of at most k literals then we say that ' is in k-CNF. Similarly, each term Ti; i = 1; : : : ; t is of the form Ti = `1 ^ ^ `s. If every term includes at most s literals then we say that ' is in s-DNF.
A truth assignment v is a function v : X ! f0; 1g. We often view a binary vector in f0; 1gn as a truth assignment that assigns the i-th bit of v to the i-th variable in X, taken in lexicographic order.
The semantics of a Boolean expression ' are captured by its set of satisfying assignments M ('), the assignments which make the expression true. It is well known that for every Boolean expression there exist equivalent (i.e., with the same set of satisfying assignments) expressions in CNF and DNF. In this case the expression ' is called CNF (respectively, DNF) expressible and similarly, k-CNF (k-DNF) expressible when the number of literals in each clause (term) is bounded by k. We also call a set M f0; 1gn of binary vectors, a kCNF set, if M is exactly the set of satisfying assignments of some k-CNF expression. Similarly for a kDNF set. We also use the notation M to denote the set f0; 1gn n M i.e., the set of all n-dimensional vectors not in M .
Given a Boolean expression ' de ned on a set of Boolean variables X, a random restriction of ', denoted ' j is the Boolean expression obtained by randomly selecting with probability p every variable and assigning each selected variable the value 0 or 1 each with probability 1/2. Therefore, a random restriction maps each variable x to the set f0; 1; g with the following probability distribution.
Pr( (x) = 0) = Pr( (x) = 1) = p=2;
Pr( (x) = ) = 1 p By (x) = we denote the event that x was not selected by .
The following is a de nition from [KS99] that we shall need later.
Let n be a positive integer and let M f0; 1gn be a set of Boolean vectors. For k > 1, we say that a Boolean vector v 2 f0; 1gn is k-compatible with M if for any sequence of k positions 0 i1 < : : : < ik n, there exists a vector in M that agrees with v in these k positions.
The above de nition implies that a vector m 2 f0; 1gn is not k-compatible with a set of Boolean vectors M if there exists a sequence of k positions in m that does not agree with any vector of M . 3
The object of this paper is to show the following proposition.
Lemma 3.1 (Hastad's Switching Lemma). Let ' be a k-CNF expressible Boolean expression. Let restriction that selects a variable of ' with probability p. Then for every s 2. be a random Pr(' j is not s-DNF) (5k(1 p))s Instead of studying the e ects of the restriction on the expression ' itself, we shall study the set M (') of satisfying assignments of '. To this end, the following result from [KS99] will prove useful. Lemma 3.2 Let M (a) M is a kCNF set.
f0; 1gn be a set of binary vectors. Then the following are equivalent: (b) If m 2 f0; 1gn is k-compatible with M , then m 2 M .
By De Morgan's rule the negation of a k-DNF expression ' is k- CNF and since M (:') = f0; 1gn n M ('), we immediately get the symmetric lemma to the above. (a) M is a kDNF set. Let M be the set of models of the expression ' (we shall henceforth use the simpler notation M instead of M (') when no confusion arises) and let us x the variable x of ' to a certain value, say 0. Obviously any model in M with value x = 0, with this value in the position of x projected out, is a model of ' jx=0. Conversely, any model of ' jx=0 augmented by the value 0 in the position of x (taken lexicographically), belongs in M . This observation is easily extended to any number of variables and hence the following fact holds.
Fact. The set of models of ' j follows from M by selecting every model in M that agrees with in every variable selected by and projecting out all positions corresponding to these variables. By also dropping out any multiple appearence of a truncated vector, we get the set of models of ' j . Let us denote for simplicity by N this set of models of ' j . We call the above procedure on a set of binary vectors M a random restriction on M and denote it by M j , extending the notion to binary vectors. Therefore N = M j .
Using the above notation and Lemmas 2 and 3 we may reformulate Lemma 1 as follows.
Lemma 3.4 (Hastad's Switching Lemma, semantic form). Let M f0; 1gn be a set of binary vectors with the property that every vector m 2 M is not k-compatible with M . Let M j be a random restriction on M that selects a position with probability p and let N = M j . Then for every s 2.
p))s Let M be a kCNF set. By Lemma 3.2 every vector in M is not k-compatible with M and therefore it has a tuple of k positions in which it disagrees with all models in M . Let T be such a k-tuple with the corresponding values. There exist 2n k vectors that have the same values in T and all belong in M . It follows that every vector in M belongs in at least one family FT of vectors that all are produced by xing k positions to certain \disagreeing" values and assuming all possible values for the rest of the variables.
In order to understand the structure of N , it is useful to view ' as being empty initially, and consider its clauses as being added one by one. Initially, M consists of models that agree with in all positions that are selected by and have all possible values in every other position. Therefore jM j = 2t, where t is the number of non-selected variables.
Let us now add a clause C in '. First consider the case where C contains only selected variables. Now if there exists one variable of C that is assigned a satisfying value by then C is, in e ect, discarded as it does not alter M . If however C is not assigned a satisfying value, then this results in M becoming empty. We call this case as C being matched by and obviously this results in N also being empty and being a good restriction as this corresponds to a contradiction.
Let us now add a clause C whose variables are not all selected by . Let V1 be the set of variables of C selected by and V2 the rest. As before if assigns a satisfying value to a variable of V1, C again has no e ect in M as it is satis ed. But if gives falsifying values to all variables of V1, then the unset variables of V2 now form a new constraint. Therefore any vector that falsi es all these variables is excluded from N and it is included in N . It follows that every vector in N belongs in at least one family FCi of vectors that are produced by xing the positions of the unset variables of the clause Ci to certain disagreeing values. The structure of N is therefore similar to that of M but with the constraints in the role of the clauses.
In summary therefore, a random restriction assigns values from f0; 1; g to the variables of ' and it may have the following results on a clause C of '.
i. It hits all of the variables of C by a falsifying value. In this case C 0 and therefore is good. ii. It hits C assigning a satisfying value to at least one of its variables. In this case C ' j .
iii. It partially hits some (or none) of the variables of C by falsifying values. The rest of the variables are not hit (they are assigned *) and now form a clause of ' j with falsifying values those of the same variables of C. We say that in this case C survives from .
Of the above three listed cases only the rst allows us to immediately decide whether (ii), completely removes C and therefore reduces the size of the instance by one clause.
is good or bad. Case It is therefore the third case that is the most interesting. Let us denote by ` the number of surviving clauses.
It is clear from the above that ' j has reduced to a CNF expression with ` clauses, those who have survived from and in general each is a sub-clause of a clause of '. If ' j is unsatis able then is obviously a good restriction. If now ' j is satis able, consider applying the distributive law of conjunction. We get a DNF expression and since we assumed that ` clauses have survived, each term of this expression may have up to ` literals, i.e. it is an `DNF expression. We have thus shown the following.
Lemma 3.5 If ` s clauses survive in ' j then
is a good restriction.
will not be `DNF expressible unless the same literal appears in several clauses. It
is clear therefore that
Notice that in some cases, as for example the case where all clauses of ' are disjoint, the above relation holds as equality and we are able to calculate the exact probability of a bad restriction.
In the next section we calculate the above probability of the case where all clauses of ' are disjoint and outline how to bound the probability of ` > s for the general case. 4
In the previous section we have summarized the e ects of on a clause C. Let us calculate now the corresponding probabilities i. A clause C, containing k literals is falsi ed when has selected all its variables with a falsifying value to every one. The probability that a variable is selected and assigned a falsifying value is obviously p2 and hence Pr(C 0) = ( p2 )k: ii. By the above, it follows that the probability that at least one of the variables is assigned a satisfying value is 1 (1 p2 )k and therefore Pr(C 1) = 1 (1 p2 )k: iii. Let us denote this probability by Ps. By the above and since the three events partition the sample space, we get that Pr(C survives from ) = Ps = (1 p2 )k ( p2 )k: When all clauses of ' are disjoint, then selecting a variable by in a clause C, is independent from selecting a variable in any other clause. In this case, is good i up to s clauses survive and this probability is calculated as follows.
Let m be the number of clauses of '. If at least one of them is matched (falsi ed) by then is good. By case (i) above, this probability is ( p )k for a speci c clause C and hence, the probability that at least one clause 2 C (among the m clauses of ') is falsi ed is Pr(at least one C is matched by ) = Pm = 1 (1 ( p2 )k)m:
The other possibility (which is disjoint from the above) for being good, is to have at most s clauses survive in ' j and the rest of them not survive (by assigning to at least one variable of each clause a satisfying value). This probability for a speci c selection of j clauses is Psj (1 (1 p2 )k)m j . Since the variable sets of any two clauses are disjoint, we simply need to sum over all possible selections of j clauses for 0 j s. We thus have and therefore,
Pr(' j is not sDNF)) = (1
s Pr(' j is sDNF)) = Pm + X
j=0 p k m ( ) ) 2 m j
s X j=0
Psj (1 (1 p )k)m j 2 m j
Psj (1 (1 p )k)m j : 2 It is easy to verify that indeed the previous probabiblity is strictly less than (5k(1 p))s.
The general case is more involved as the independence in selecting a variable between two clauses does no longer hold.
Let ` be the number of surviving clauses of ' after the application of . Let m be the number of clauses of ' and let us denote by e('; s) the event that exactly ` = s clauses survive in ' j and all the rest m s are satis ed. Let us also denote by E('; s) the event that ` > s clauses survive in ' j and all the rest m ` are satis ed. We would like to show that
Pr(E('; s)) (5k(1 p))s
Base. For m = 1, Pr(` s + 1) = 0 for every s 1.
Step. For m > 1 let us assume that for every kCNF expression with up to m 1 clauses (on any number of variables), Lemma 4.1 holds. Consider a kCNF expression ' with m clauses. Let C be one of its clauses. For ease of reference, we denote by '0 = ' n C (that is, the expression that results from ' when we remove C) and by Hs = (5k(1 p))s.
We now have
Pr(E('; s)) = Pr(e('0; s) ^ (C survives)) + Pr(E('0; s) ^ (C 6 0)) Note that when more than s clauses have survived in '0, C must not be false in order to have a bad restriction. The event C 6 0 includes both the event C 1 and the event C survives. The rst term is simpli ed as follows. Let A be the set of assignments to the variables of C from the set f0; 1; g that make C survive. Let be an assignment from f0; 1; g to the variables of C. We denote by e( ) the event that assigns the values of to the variables of C.
Pr(e('0; s) ^ (C survives)) = Pr(e('0; s) ^ _ e( )) = Pr( _ (e('0; s) ^ e( ))) 2A X Pr(e('0; s) ^ e( )) 2A X Pr(E('0; s 2A
2A X Pr(E('0; s 2A
1) ^ e( )) = 1) j e( )) Pr(e( )) The last inequality holds since the second event contains the rst. Observe now that if we substitute to the variables of C any values from f0; 1; g, some clauses of '0 may be satis ed and thus removed from '0, and some variables may be removed from the remaining clauses either because they are unsatis ed, or they are assigned *. In any case the resulting CNF has at most m 1 clauses with at most k literals each and thus by induction Lemma 4.1 holds. There is a problem however that stems from the conditional probability: by setting speci c values to some variables of ', we no longer have a restriction with the same distribution for the remaining variables. There are ways to overcome this complication by splitting the assignment of values to speci c sets of variables and summing over all possible such sets. The reader is referred to the original proof of Hastad or in [BS90]. Using these techinques we have
X Pr(E('0; s 2A 1) j e( ))
Hs 1
X Pr(E('0; s 1) j e( )) Pr(e( ))
Hs 1
X Pr(e( )) = Hs 1Ps; 2A 2A since the sum of the probabilities is over all assignments that make C survive. Similarly, the second term gives
Pr(E('0; s) ^ (C 6 0))
Hs(1 Hs 1Ps + Hs(1
p k ( ) )
2 1 p k 2 (5k(1 or equivalently [Ajt83]
M. Ajtai. This last inequality is easily shown by rst proving that the left-hand side is an increasing function of k for all p 2 [0:8; 1] and thus by substituting the smallest permissible value of k = 2, it su ces to show that the produced function of p is increasing and positive for p = 0:8. This is indeed the case and it can be shown by taking the derivative over p.
formulae on nite structures. Annals of Pure and Applied Logic, 24:1-48, 1983. [Has86] J. Hastad. Almost optimal lower bounds for small depth circuits. STOC, 6-20, May 1986.