tag:blogger.com,1999:blog-786333285568106173.post3576720444518512532..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: A Technical LemmaMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-786333285568106173.post-78373088935721328342009-09-21T03:01:04.500-04:002009-09-21T03:01:04.500-04:00Oh, silly me.
Thanks a lot!
-ConfusedGradStudent...Oh, silly me.<br /><br />Thanks a lot!<br /><br />-ConfusedGradStudentAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-6885941794334570612009-09-20T19:48:30.827-04:002009-09-20T19:48:30.827-04:00@ConfusedGradStudent: I am certainly happy that pe...@ConfusedGradStudent: I am certainly happy that people are reading my papers :)<br /><br />There is indeed a factor of t! (I think even a bit worse, i.e. 2^O(tlg t) with a bigger constant).<br /><br />But consider that t=O(lg n) [for t=lg n, there is nothing to prove, as we have a solution with O(1) redundancy]<br /><br />Also, w=Omega(lg n). Thus, w^O(t) is in fact the same as w^O(t) * t!Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-27576213787791821802009-09-20T09:11:30.634-04:002009-09-20T09:11:30.634-04:00sorry, I meant
"however, I get r . w^O(t) . ...sorry, I meant <br />"however, I get r . w^O(t) . factorial(t) > n,"<br /><br />i.e. your bound divided by t factorial.<br /><br />ThanksAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-73365029592614799842009-09-20T08:06:38.868-04:002009-09-20T08:06:38.868-04:00Dear Mihai,
I've got a question about the Sod...Dear Mihai,<br /><br />I've got a question about the Soda paper associated with this post.<br /><br />Suppose we have a static data structure for rank queries that takes up n+r bits. Let w be the number of bits in a word.<br /><br />Through a probe elimination lemma you prove that r.w^O(t) > n. When I carry out the calculations however, I get r . w^O(1) . factorial(t) > n, which is a substantially weaker bound for super-constant t.<br /><br />You claim that P_{i+1} = k_i . O(w). However I think it should be t times that since Probes(Q_0) = k_i . t_i, where t_i is the number of probes in the induction.<br /><br />I checked this with a couple of friends here but we couldnt get this. Your help would be greatly appreciated. ThanksConfusedGradStudentnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-32303966275743258182009-09-07T11:49:20.104-04:002009-09-07T11:49:20.104-04:00@Mihai: Thanks, I can follow that. (Late reply bec...@Mihai: Thanks, I can follow that. (Late reply because I've been traveling.)rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-78745195166182994772009-08-26T23:43:59.737-04:002009-08-26T23:43:59.737-04:00Actually, the anon has a good point. I won't ...Actually, the anon has a good point. I won't agree that intuition should categorically be kept out of begin/end proof. But generally it should be kept separate from the technical steps. Acceptable solutions are: putting it all before or immediately after the begin{proof} (depending on which works better), using remarks, or having separate paragraphs of intuition within the proof. What does not work is mixing sentences of intuition with formal sentences inside the proof. This easily becomes very confusing.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-55323878507747536402009-08-26T15:15:11.214-04:002009-08-26T15:15:11.214-04:00Anon, I don't think we should take the intuiti...Anon, I don't think we should take the intuition outside the proofs, since they do tend to get long at times... Since you claim a good understanding of what a competent mathematician does, let me add that the competent TCS person only reads the intuition, if at all :)<br /><br />Once we switch to electronic publishing, we might require that all formal claims in a proof are typeset in black, and all intuition in blue. But it would be bad to separate them.<br /><br />In any case, the typical problem is that proofs are unreadable for being too technical, not unreadable because of too many explanations :)Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-46162914828416845052009-08-26T12:13:37.852-04:002009-08-26T12:13:37.852-04:00rgrig, for the Ω(lg n) part, you remember that the...rgrig, for the Ω(lg n) part, you remember that the binomial has mass Ω(1/sqrt(n)) on all values in n/2 ± sqrt(n). This follows from Sterling (but is a very useful thing to remember).Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-26270712709274565622009-08-26T11:06:08.341-04:002009-08-26T11:06:08.341-04:00@Pat Morin: Thanks for the link!
@Mihai: I unders...@Pat Morin: Thanks for the link!<br /><br />@Mihai: I understand the "Wikipedia is good enough" point of view, but it bothers <i>me</i> not to know where the result comes from :) (And <i>you</i> said we should ask for help if we need it, right? :p)<br /><br />I didn't try to get the constant. I tried to get h(n)=Θ(lg n). The part h(n)=O(lg n) is easy, since you can put the count in an int with lg n bits. For the part h(n)=Ω(lg n) I tried to show h(n+1)-h(n)=Ω(1/n). But the difference still looks horrible. It feels like there <i>must</i> be some easy way to get h(n)=Θ(lg n), doesn't it?rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-40408448823923131932009-08-26T11:01:32.357-04:002009-08-26T11:01:32.357-04:00On the off chance that you are serious, you are ve...<i><br />On the off chance that you are serious, you are very seriously mistaken. Highly technical writing without a crisp explanation of why the math should hold has turned out to be wrong often enough.<br /></i><br /><br />No I was not joking and you misunderstand my point. Mathematical papers should have<br />Definitions, Theorems, Proofs, as well as other explanatory texts (serving as Introduction, Summary of the main ideas, even philosophy etc.). However, just as there should not be any irredundancy and loose words in the Definitions and statements of the Theorems, the same should ideally hold for the proofs as well.<br /> <br />Of course you are free to be as verbose as you like outside <br />\begin{proof} ... \end{proof}<br />but a capable mathematical reader should be free to ignore this verbosity and still be able to understand the proof.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-33930220736106877502009-08-25T20:14:01.447-04:002009-08-25T20:14:01.447-04:00Anon, I hope you are joking, in which case the del...Anon, I hope you are joking, in which case the delivery is quite good. On the off chance that you are serious, you are very seriously mistaken. Highly technical writing without a crisp explanation of why the math should hold has turned out to be wrong often enough.<br /><br />Rgrig, by concentration I almost always mean the Chernoff bound :) Other concentration results that I have used are Azuma, Johnson-Lindenstrauss, and various tricks with finite moments.<br /><br />As for the Wikipedia step, I do not need to calculate the exact constant. All I need is that, as I go from m trials to 2m trials, the entropy increases by Omega(1), which is pretty natural if your entropy behaves like c*lg n. Thus, I was not particularly interesting in reworking the entropy of the binomial; Wikipedia is good enough.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-67706551321894377172009-08-25T19:09:11.703-04:002009-08-25T19:09:11.703-04:00@rgrig
Here's a good survey paper about conce...@rgrig<br /><br />Here's a good survey paper about concentration inequalities:<br /><br />http://tinyurl.com/lmyn44<br /><br />of the kind Mihai is referring to.Anonymoushttps://www.blogger.com/profile/06328185728688465505noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-76513949365829739612009-08-25T14:19:51.455-04:002009-08-25T14:19:51.455-04:00OK, here's a very informal argument for the fi...OK, here's a <b>very</b> informal argument for the first lemma. I put it here because you said you want to convey intuitions and I would have liked reading this before your proof.<br /><br />Q_Δ is made out of k numbers in the range 0..n/k so it takes k lg n/k bits.<br />To encode (Q_0,Q_Δ) we can use 2k numbers in the range 0..n/2k for a total of 2k lg n/2k = 2k lg n/k - 2k bits.<br /><br />We have 2(k lg n/k) - (2k lg n/k - 2k) = 2k fewer bits when we encode Q_0 together with Q_Δ.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-78531280063994708432009-08-25T10:06:03.298-04:002009-08-25T10:06:03.298-04:00I think mathematical proofs should be succint, [.....<i>I think mathematical proofs should be succint, [...] and <b>avoid talking about intuition</b></i><br /><br />I think that's why non-mathematicians throw up their arms and wonder if mathematicians are humans or machines. :p I'm not a TCS person and I very much enjoy reading posts in this style, which I can follow.<br /><br />@Mihai: I read this to see if I remember anything from my probability courses. I got stuck at the Wikipedia step. I know I shouldn't "agonize" over a "well-known" result :) but I couldn't figure out an easy way to compute sum((n choose k) lh (n choose k)) and that bothers me.<br /><br />Also, I think I never knew what "probability concentration" is and google results are lacking in tutorial-style material on this subject. Any pointers?<br /><br />And thanks for posting this.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-63981637223116595522009-08-24T18:38:20.255-04:002009-08-24T18:38:20.255-04:00Proofs written like this (verbose style) causes ma...Proofs written like this (verbose style) causes mainstream probabilists to often throw up their arms and start doubting if TCS people know what they are doing. I think mathematical proofs should be succint, lay out all or most of the steps, and avoid talking about intuition etc. If the proof is long it should be broken into steps using lemmas and/or propositions.<br />If something regarding the idea (or ideas) behind the proof needs to be explained, it can be done under a separate heading or as "Remarks". Mixing these things is usually not a good idea and should be discouraged as bad practice. TCS authors often indulge in this bad practice. The resulting proofs become error prone, difficult to verify, and then become subject of criticisms from people like Neal Koblitz (just one example, but ask almost any mathematician who tried to read TCS papers).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-26403618476365871782009-08-24T14:18:30.325-04:002009-08-24T14:18:30.325-04:00Paul, very good idea of describing the intuition a...Paul, very good idea of describing the intuition as an upper bound.<br /><br />Anon: I did not skip the proof of this lemma (that would be quite dangerous, as things in lower bounds are often tricky). The problem was that my description was too succinct for a reader who had not done this before — and of course, that it used words like "clearly" and "standard." As I always complain, if you write "X", the referee finds it an obvious step, but if you write "One immediately sees that X", the referee says this is not obvious and a proof is needed.<br /><br />The requirement to include full proofs is a good rule of thumb (and I actively advocated for it in the FOCS committee). But you cannot treat it as absolute: the readers are not theorem checkers, and what is a good proof for one, is something undecyphrable for another.<br /><br />The main benefit of the complete-proofs rule is that the steps are formally stated. And then, the paper becomes falsifiable — a big difference.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-59977050992851502012009-08-24T00:37:27.578-04:002009-08-24T00:37:27.578-04:00I would be more motivated to read this post if you...I would be more motivated to read this post if you told us what the main result of the paper is.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-944008260424357652009-08-23T22:19:15.470-04:002009-08-23T22:19:15.470-04:00A complete proof should include both the forest an...A complete proof should include both the forest and the trees. Since you did not follow the submission guidelines, I am surprised that they let you modify your submission during the refereeing process. For fairness they should have rejected it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-68185203576877091842009-08-23T16:22:58.490-04:002009-08-23T16:22:58.490-04:00Thumbs up on your explanation overall.
A minor ...Thumbs up on your explanation overall. <br /><br />A minor comment: Your first intuition point about knocking off εk-bits at most (which you later rescind) might be better expressed as an upper bound rather than a lower bound: "that's the most you can be expected to tolerate" because an adversary might reduce them by this much. Your point later in the proof is that an adversary might succeed even better than this if the entropy were distributed unevenly, but that doesn't contradict the right version of the intuition.<br /><br /><i>But what exactly is straightforward is in the eye of the beholder, and one of the referees did not like my (succinct and semicoherent) proof. I was thus asked to provide as detailed an explanation as I could, pronto.</i><br /><br />Given the SODA call for papers it this shouldn't have been a surprise. The SODA CFP contains<br />"<b> The submission must contain complete proofs. (Part of the proofs can be relegated to the appendix if they do not fit in the requisite number of pages.)</b>" <br />"Straightforward" in the eye of the prover does not equal "complete". This is one of those lemmas that someone familiar with typical arguments in the area would expect to be true but that is different from having a "complete proof".<br /><br />This requirement is likely going to be the norm for the future and seems to be a positive step. It will of course reduce some of the macho "I did the whole thing the night before" in future but that isn't much of a loss.Paul Beamenoreply@blogger.com