tag:blogger.com,1999:blog-3722233.post414287016241045560..comments2020-02-16T18:25:33.023-05:00Comments on Computational Complexity: A Kolmogorov Complexity Proof of the Lovász Local LemmaLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-8645560840690190892017-05-19T07:53:29.412-04:002017-05-19T07:53:29.412-04: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-10T16:32:57.889-05:002013-11-10T16:32:57.889-05: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-10T16:27:04.874-05:002013-11-10T16:27:04.874-05: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-10T14:19:05.392-05:002013-11-10T14:19:05.392-05: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-05T03:29:43.865-04:002009-06-05T03:29:43.865-04: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-04T16:25:51.080-04:002009-06-04T16:25:51.080-04: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-04T08:47:42.083-04:002009-06-04T08:47:42.083-04: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-03T14:29:03.037-04:002009-06-03T14:29:03.037-04: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-03T14:04:52.683-04:002009-06-03T14:04:52.683-04: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-03T12:54:33.859-04:002009-06-03T12:54:33.859-04: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-02T19:29:35.389-04:002009-06-02T19:29:35.389-04: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-02T17:41:44.807-04:002009-06-02T17:41:44.807-04: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-02T12:02:09.635-04:002009-06-02T12:02:09.635-04: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-02T10:10:24.477-04:002009-06-02T10:10:24.477-04: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-02T10:05:59.556-04:002009-06-02T10:05:59.556-04: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-02T09:29:05.060-04:002009-06-02T09:29:05.060-04: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-02T07:58:50.008-04:002009-06-02T07:58:50.008-04: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