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.

## Friday, March 2, 2007

Subscribe to:
Post Comments (Atom)

## 1 comment:

I just found the website who reviews about

Several

home business ideas

If you want to know more here it is

home business reviews

www.home-businessreviews.com

Post a Comment