Switching Lemmas

Petar asked me some questions about the switching lemma
that reminded me that I had not provided enough context
or background about this lemma to you. (By the way at the
bottom of this post I've added a glossary of terms used ...
that may be helpful to scan before reading the rest of this
post.)

The lemma, as proven in class, stated that for
every poly p, there exists a constant C = C_p
such that a DNF formula on n variables with
size s=p(n) can be converted into
a CNF formula on C variables (and hence of size ~ 2^C)
by hitting it with a restriction that leaves a variable
unset with probability sqrt{n}.

The proof went in two stages: The first used the
restrictions to reduce the length of terms, to say c. The
second stage then applied only to c-DNF formulae.

In the stronger switching lemmas (e.g., Hastad's) one
assumes that the formula is already a c(n)-DNF formula
and shows that this can be converted to a C(n)-CNF formula
after the restriction. For example, one may start with
a log^2 n-DNF formula and prove that after the switch
it is a log^3 n CNF formula ...

Several points to note here:
1. One does not assume a size bound on the DNF formula
explicitly. But a bound is implicit anyway, since the
length is at most n^{c(n)}.

2. The lemma does not prove explicitly that the final
function is a function of a small number of variables
... however your problem set 2 (problem 3) will show why
the function does't depend on a number of variables that
is function only of c(n) and C(n) and not n directly.

3. The proof of the stronger versions of the switching
lemma is much harder ... one needs to argue that the
c(n)-DNF formula does not have any maxterms of length
greater than C(n)+1 after it is hit with a restriction.

I personally like Hastad's proof (from his Ph.D. thesis)
which I found intuitive, though it has some tough
calculations. Razborov's proof is more subtle,
shorter but less intuitive to me. Paul Beame's survey on
switching lemma's is probably a great source to read all
this from (I haven't read it yet ... thats why its on
the list of projects!).

Petar also pointed to a proof in the book on Kolmogorov
Complexity by Li and Vitanyi which rephrases Razborov's
proof of Hastad's switching lemma. The proof uses the
language of "incompressibility", which roughly says that
there is no way to compress 2^k + 1 strings into k bits.
Using "incompressibility" in your proofs versus
"counting + pigeonhole principle" is a matter of aesthetics
(sort of like using probabilities, versus cardinality of sets).
If the proof suits you better you are welcome to it, though
often there is a line-to-line translation without using the
phrase "incompressible".


I ought to add references here ... but am tiring myselves out.
So will do so later. (Or someone could do so as a comment.)

- Madhu


Glossary:

A literal is a variable or its negation.

A term is a conjunction of literals.

A clause is a disjunction of literals.

A k-DNF has terms of length at most k (at most k literals per term);

An l-CNF has clauses of length at most l.

A term (l1 and l2 and ... lk) is called a minterm of a function
f, if setting l1 = l2 = ... lk = 1 sets f to 1, and {l1 ... lk}
is minimal with respect to this property.

A maxterm is a clause (l1 or l2 .. or lk) with the property that
setting all literals to false falsifies the function, and
{l1 ... lk} is minimal with respect to this property.