My solution to Problem 4 in Problem Set 2 is an adaptation of Hirsch'98. This solution is somewhat dissimilar to Sipser-Saxe-Furst (contrary to what the hint in the Problem Set suggests) and so I wonder if someone has a different (easier) solution.
On the other hand, reading Hirsch's paper raised an interesting question. As a corollary of this exercise we know that formulas with bounded-width clauses and many satisfying assignments have short (constant size) partial satisfying assignments. It is an open question (according to Hirsch) whether a similar procedure exists for CNF formulas with unbounded-width clauses.
To suggest that maybe this is not possible, (in Remark 6 of Hirsch'98) Hirsch constructs a CNF for which more than half of all assignments are satisfactory and yet for every partial assignment on SQRT(n) variables there exists a corresponding complete assignment which is unsatisying.
Hirsch, however, fails to point out that the constructed CNF formula might (and most likely will) be exponential in size. This raises a new, more concrete, open question: Is there a way to modify the present algorithm such that it takes advantage of bounds on formula length in addition to clause-width that solves the problem for CNFs with unbounded-width clauses in sub-exponential time?
Sunday, March 11, 2007
Friday, March 2, 2007
Looking for Partners for Projects?
If you are looking for a partner for your project, post a comment below or look at the other comments.
Incorrect attribution for rank bound
In lecture on Wednesday, 2/28/2007, I asserted that the
communication complexity of a function f is lower bounded
by the log of the rank of the associated matrix M_f.
I then attributed this to Yao.
The attribution was incorrect. Nick Harvey pointed out
to me that the source of this lower bound is Mehlhorn
and Schmidt, STOC 1982. (Thanks to Nick for correcting
me.)
Nick also pointed out that my explanation of the
"tiling lower bound" was not clear (I agree). I
will try to post additional notes to clarify this.
Also I should have mentioned that the book "Communication
Complexity" by Kushilevitz and Nisan is an excellent place
to read more about the topic.
- Madhu
communication complexity of a function f is lower bounded
by the log of the rank of the associated matrix M_f.
I then attributed this to Yao.
The attribution was incorrect. Nick Harvey pointed out
to me that the source of this lower bound is Mehlhorn
and Schmidt, STOC 1982. (Thanks to Nick for correcting
me.)
Nick also pointed out that my explanation of the
"tiling lower bound" was not clear (I agree). I
will try to post additional notes to clarify this.
Also I should have mentioned that the book "Communication
Complexity" by Kushilevitz and Nisan is an excellent place
to read more about the topic.
- Madhu
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.
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.
Subscribe to:
Posts (Atom)