tag:blogger.com,1999:blog-3722233.post414287016241045560..comments2021-04-20T09:52:56.297-05:00Comments on Computational Complexity: A Kolmogorov Complexity Proof of the Lovász Local LemmaLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-37009581361556418682021-03-19T06:25:57.445-05:002021-03-19T06:25:57.445-05:00Fix(C)
Replace the variables of C with new random ...Fix(C)<br />Replace the variables of C with new random values<br />While there is clause D that shares a variable with C that is not satisfied<br /> Fix(D)<br /><br />It is in the second part: if to clauses X and Y that overlap then Y will be in one of the D that will be fixed. Assuming Fix(C) terminate the previously satisfied clauses remain satisfied.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8645560840690190892017-05-19T06:53:29.412-05:002017-05-19T06:53:29.412-05:00I know this is an old post, but I'm still miss...I know this is an old post, but I'm still missing part of the argument, namely the running time bound.<br /><br />For some sources of randomness the algorithm will finish sooner, for some later -- this makes thinking about s as universal number for every x a bit vague. My understanding is that one needs to bound the expectation of the running time -- is it somehow hidden in the assumption that x is Kolmogorov random string? Or is more work needed?<br /><br />I also noticed that the paper by Moser and Tardos use somewhat different algorithm, one that avoids recursion.<br />Is it just a presentation detail, or do the two algorithms have different running times? Or is this the version<br />from the talk as opposed to the paper?<br />Roberthttps://www.blogger.com/profile/03214385345519260084noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64465096149536825992013-11-10T15:32:57.889-06:002013-11-10T15:32:57.889-06:00It's not that simple. Best to read the paper.It's not that simple. Best to read the <a href="http://dl.acm.org/citation.cfm?doid=1667053.1667060" rel="nofollow">paper</a>.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59111120845451741292013-11-10T15:27:04.874-06:002013-11-10T15:27:04.874-06:00I changed it to be just "s".I changed it to be just "s".Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66068202135681038902013-11-10T13:19:05.392-06:002013-11-10T13:19:05.392-06:00Can you please clarify how the constant d becomes ...Can you please clarify how the constant d becomes 3?<br /><br />Thanks in advance.Tapas Kumar Mishrahttps://www.blogger.com/profile/17133565038627940522noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80905120711146605442009-06-05T02:29:43.865-05:002009-06-05T02:29:43.865-05:00Presumably you meant "at most s" instead...Presumably you meant "at most s" instead of "at least s"?András Salamonhttp://constraints.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77564987060332033672009-06-04T15:25:51.080-05:002009-06-04T15:25:51.080-05:00Moser's proof reminds me of the Chronogram Met...Moser's proof reminds me of the Chronogram Method in Data Structure Lower Bounds. Another coding argument that gives a lower bound, in a similar way.eladnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73269953856992311092009-06-04T07:47:42.083-05:002009-06-04T07:47:42.083-05:00Nice post. But I never understand why such argumen...Nice post. But I never understand why such arguments are said to use "Kolmogorov complexity". It looks like straight information theory to me.Jonathan Katzhttps://www.blogger.com/profile/07362776979218585818noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10752862865381216882009-06-03T13:29:03.037-05:002009-06-03T13:29:03.037-05:00We can describe the C such that Fix(C) is called b...<i>We can describe the C such that Fix(C) is called by Solve by m log m bits</i><br><br />Use a bitstring instead of a list and it only takes m bits, so s = O(m).Namelessnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74385248880812822242009-06-03T13:04:52.683-05:002009-06-03T13:04:52.683-05:00What is an example of a formula with few satisfyin...<i>What is an example of a formula with few satisfying assignments that satisfies the hypothesis of the lemma?...</i><br><br />(avb)^(av~b)^(cvd)^(cv~d)^...<br />which you can generalize to kcnfs.Jelani Nelsonhttps://www.blogger.com/profile/00216475103758212305noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77935499610042079482009-06-03T11:54:33.859-05:002009-06-03T11:54:33.859-05:00Anon2: you are missing the fact that Fix() termina...Anon2: you are missing the fact that Fix() terminates. If the new assignment to Y un-satisfies X, Y will call Fix() on X. This might look like an infinite recursion, but the proof shows it is not.<br /><br />This one is definitely from the book. Very beautiful!Sashohttps://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21403059406604004402009-06-02T18:29:35.389-05:002009-06-02T18:29:35.389-05:00Response to last anon.
LLL was non-constructive o...Response to last anon.<br /><br />LLL was non-constructive only in the sense of efficiency. The new proof gives an efficient (poly-time) randomized algorithm as a byproduct.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7987358137774171572009-06-02T16:41:44.807-05:002009-06-02T16:41:44.807-05:00If I'm not mistaken:
Before: We had a nonconstruc...If I'm not mistaken:<br /><br />Before: We had a nonconstructive existence proof.<br />After: We have a nonconstructive proof-of-correctness for an explicit construction.<br /><br />We push the nonconstructiveness one level down. Is it possible to get rid of it completely?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37659530435649409582009-06-02T11:02:09.635-05:002009-06-02T11:02:09.635-05:00Great description of a great technique. This is m...Great description of a great technique. This is much easier than the usual inductive proofs. To me the really brilliant point is the picking of a specific Kolmogorov/Chaiten at the start and not having to deal with randomness in the insides of the argument.John Mounthttp://www.win-vector.com/blog/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54263300424501089472009-06-02T09:10:24.477-05:002009-06-02T09:10:24.477-05:00What is an example of a formula with few satisfyin...What is an example of a formula with few satisfying assignments that satisfies the hypothesis of the lemma? I.e., a formula where you would need this algorithm because picking a random assignment would not work?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6699355214747575052009-06-02T09:05:59.556-05:002009-06-02T09:05:59.556-05:00If there are two clauses, X and Y, that overlap in...<I>If there are two clauses, X and Y, that overlap in a variable, then if Y's assignment is changed so that it is satisfied, then now it is possible that X is no longer satisfied.</I>I think the while loop in Fix() iterates over C also; i.e., it's not "While there is a clause D neq C that shares ..."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91483562798053597612009-06-02T08:29:05.060-05:002009-06-02T08:29:05.060-05:00"Assume Fix(C) always terminates. Every clause tha..."Assume Fix(C) always terminates. Every clause that was satisfied before we called Fix(C) will still remain sastisfied and C will also now be satisfied."<br /><br />Why will each clause that is satisfied remain satisfied? If there are two clauses, X and Y, that overlap in a variable, then if Y's assignment is changed so that it is satisfied, then now it is possible that X is no longer satisfied. What am I missing?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77834270493054478162009-06-02T06:58:50.008-05:002009-06-02T06:58:50.008-05:00Very nice! I'm sorry to have missed this talk (and...Very nice! I'm sorry to have missed this talk (and this STOC).AChttps://www.blogger.com/profile/14911233583375020356noreply@blogger.com