tag:blogger.com,1999:blog-59306036503145944892015-09-16T11:04:58.587-07:00MIT 6.841MIT 6.841 Bloghttp://www.blogger.com/profile/05060258433867607037noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-5930603650314594489.post-35123455399819206072007-05-02T13:04:00.000-07:002007-05-02T13:07:29.156-07:00Post Comments on PCPs, Average-Case Complexity HereDear 6.841 students,<br /><br />As part of your course participation requirement, please post/send in<br />your comments on the material covered in the 3 lectures on PCPs and the 2<br />lectures on Average-case complexity.<br /><br />Here are the instructions for sending in your comments:<br /><br />The idea is to send a brief overview *in your own words*<br />of what you thought was covered. Follow this up with a few words<br />saying what you liked and what you did not like. Any other comments,<br />questions, topics to be clarified would also be welcome. Your<br />comments could range from anywhere from a couple of paras to a whole<br />volume! Post your comments on the blog at http://mit6841.blogspot.com/<br />(or email them to Swastik).MIT 6.841 Bloghttp://www.blogger.com/profile/05060258433867607037noreply@blogger.com63tag:blogger.com,1999:blog-5930603650314594489.post-52745564663204901612007-03-11T18:28:00.000-07:002007-03-11T18:49:11.847-07:00When there are many satisfying assignments ...<a href="http://pdos.csail.mit.edu/%7Epetar/courses/sudan07complexity/">My solution to Problem 4 in Problem Set 2</a> is an adaptation of <a href="http://logic.pdmi.ras.ru/%7Ehirsch/abstracts/ljigpl98.html">Hirsch'98</a>. 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.<br /><br />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 <span style="font-weight: bold;">open question</span> (according to Hirsch) whether a similar procedure exists for CNF formulas with unbounded-width clauses.<br /><br />To suggest that maybe this is not possible, (in Remark 6 of <a href="http://logic.pdmi.ras.ru/%7Ehirsch/abstracts/ljigpl98.html">Hirsch'98</a>) 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.<br /><br />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, <span style="font-weight: bold;">open question</span>: 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?Petar Maymounkovnoreply@blogger.com2tag:blogger.com,1999:blog-5930603650314594489.post-40659265301528792092007-03-02T07:54:00.000-08:002007-03-02T08:10:10.463-08:00Looking for Partners for Projects?If you are looking for a partner for your project, post a comment below or look at the other comments.MIT 6.841 Bloghttp://www.blogger.com/profile/05060258433867607037noreply@blogger.com52tag:blogger.com,1999:blog-5930603650314594489.post-29667993125233635512007-03-02T05:27:00.000-08:002007-03-02T05:34:10.869-08:00Incorrect attribution for rank boundIn lecture on Wednesday, 2/28/2007, I asserted that the<br />communication complexity of a function f is lower bounded<br />by the log of the rank of the associated matrix M_f. <br />I then attributed this to Yao. <br /><br />The attribution was incorrect. Nick Harvey pointed out<br />to me that the source of this lower bound is Mehlhorn<br />and Schmidt, STOC 1982. (Thanks to Nick for correcting<br />me.)<br /><br />Nick also pointed out that my explanation of the <br />"tiling lower bound" was not clear (I agree). I <br />will try to post additional notes to clarify this.<br /><br />Also I should have mentioned that the book "Communication<br />Complexity" by Kushilevitz and Nisan is an excellent place<br />to read more about the topic.<br /><br />- MadhuMIT 6.841 Bloghttp://www.blogger.com/profile/05060258433867607037noreply@blogger.com0tag:blogger.com,1999:blog-5930603650314594489.post-91405393569255225332007-03-02T05:16:00.000-08:002007-03-02T05:21:23.519-08:00Switching LemmasPetar asked me some questions about the switching lemma<br />that reminded me that I had not provided enough context<br />or background about this lemma to you. (By the way at the<br />bottom of this post I've added a glossary of terms used ...<br />that may be helpful to scan before reading the rest of this<br />post.)<br /><br />The lemma, as proven in class, stated that for<br />every poly p, there exists a constant C = C_p<br />such that a DNF formula on n variables with<br />size s=p(n) can be converted into<br />a CNF formula on C variables (and hence of size ~ 2^C)<br />by hitting it with a restriction that leaves a variable<br />unset with probability sqrt{n}.<br /><br />The proof went in two stages: The first used the<br />restrictions to reduce the length of terms, to say c. The<br />second stage then applied only to c-DNF formulae.<br /><br />In the stronger switching lemmas (e.g., Hastad's) one<br />assumes that the formula is already a c(n)-DNF formula<br />and shows that this can be converted to a C(n)-CNF formula<br />after the restriction. For example, one may start with<br />a log^2 n-DNF formula and prove that after the switch<br />it is a log^3 n CNF formula ...<br /><br />Several points to note here:<br />1. One does not assume a size bound on the DNF formula<br />explicitly. But a bound is implicit anyway, since the<br />length is at most n^{c(n)}.<br /><br />2. The lemma does not prove explicitly that the final<br />function is a function of a small number of variables<br />... however your problem set 2 (problem 3) will show why<br />the function does't depend on a number of variables that<br />is function only of c(n) and C(n) and not n directly.<br /><br />3. The proof of the stronger versions of the switching<br />lemma is much harder ... one needs to argue that the<br />c(n)-DNF formula does not have any maxterms of length<br />greater than C(n)+1 after it is hit with a restriction.<br /><br />I personally like Hastad's proof (from his Ph.D. thesis)<br />which I found intuitive, though it has some tough<br />calculations. Razborov's proof is more subtle,<br />shorter but less intuitive to me. Paul Beame's survey on<br />switching lemma's is probably a great source to read all<br />this from (I haven't read it yet ... thats why its on<br />the list of projects!).<br /><br />Petar also pointed to a proof in the book on Kolmogorov<br />Complexity by Li and Vitanyi which rephrases Razborov's<br />proof of Hastad's switching lemma. The proof uses the<br />language of "incompressibility", which roughly says that<br />there is no way to compress 2^k + 1 strings into k bits.<br />Using "incompressibility" in your proofs versus<br />"counting + pigeonhole principle" is a matter of aesthetics<br />(sort of like using probabilities, versus cardinality of sets).<br />If the proof suits you better you are welcome to it, though<br />often there is a line-to-line translation without using the<br />phrase "incompressible".<br /><br /><br />I ought to add references here ... but am tiring myselves out.<br />So will do so later. (Or someone could do so as a comment.)<br /><br />- Madhu<br /><br /><br />Glossary:<br /><br />A literal is a variable or its negation.<br /><br />A term is a conjunction of literals.<br /><br />A clause is a disjunction of literals.<br /><br />A k-DNF has terms of length at most k (at most k literals per term);<br /><br />An l-CNF has clauses of length at most l.<br /><br />A term (l1 and l2 and ... lk) is called a minterm of a function<br />f, if setting l1 = l2 = ... lk = 1 sets f to 1, and {l1 ... lk}<br />is minimal with respect to this property.<br /><br />A maxterm is a clause (l1 or l2 .. or lk) with the property that<br />setting all literals to false falsifies the function, and<br />{l1 ... lk} is minimal with respect to this property.MIT 6.841 Bloghttp://www.blogger.com/profile/05060258433867607037noreply@blogger.com1tag:blogger.com,1999:blog-5930603650314594489.post-5176559827587882312007-02-16T10:43:00.000-08:002007-02-16T10:45:15.963-08:00Welcome to MIT 6841 BlogHi All<br /><br />Welcome to the Blog site for MIT 6.841.<br /><br />We'll use this site to ask/answer queries about lectures.<br />If you post questions here, please also email the staff<br />(madhu and swastik).<br /><br />Take care<br /><br />- Madhu & Swastik.MIT 6.841 Bloghttp://www.blogger.com/profile/05060258433867607037noreply@blogger.com2