tag:blogger.com,1999:blog-3722233.post4028663037837763749..comments2023-03-23T09:50:46.959-05:00Comments on Computational Complexity: Wassily Hoeffding 1914-1991Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-33415132283173733112014-06-15T13:28:21.510-05:002014-06-15T13:28:21.510-05:00Shouldn't the question be who _last_ phrased t...Shouldn't the question be who _last_ phrased the term `The Columbus Principle'? ;)ke^kxhttps://www.blogger.com/profile/14857482244757489959noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66078814173538569742014-06-13T11:31:51.850-05:002014-06-13T11:31:51.850-05:00The Columbus Principle: things are named after the...The Columbus Principle: things are named after the last person who discovered them (Columbus was the last person to ``discover'' america).<br /><br />Trivia: Who first phrased the term `The Columbus Princeiple' ?GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85767603761250834782014-06-13T11:29:14.399-05:002014-06-13T11:29:14.399-05:00Enough with this canard that we name things after ...Enough with this canard that we name things after their discoverer. Naming conventions in math/CS are fairly random. For very many results we can find earlier references that foretell if not totally pre-discover the result. It's the nature of the scientific endeavour that many people will converge to the same result independently and that some of these efforts will get more attention than others leading to naming rights.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53533435381633502582014-06-12T16:35:08.412-05:002014-06-12T16:35:08.412-05:00Hoeffding's inequality is, I believe, more gen...Hoeffding's inequality is, I believe, more general. It says that if X=X_1+X_2+...+X_n for a_i <= X_i <= b_i for real numbers a_i and b_i, then P(E[X]-X >= epsilon * n) <= exp(2*n^2*epsilon^2 / ((a_1-b_1)^2+...+(a_n-b_n)^2)). (Sorry for poor formatting.)<br /><br />(Disclaimer: I read Hoeffding's original paper several months ago, but I never read Bernstein's paper you refer to, so I'm not sure what exactly he published. Based on Wikipedia, it seems his result is less general.)blazshttp://blazsovdat.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17876791531400373452014-06-12T12:57:09.725-05:002014-06-12T12:57:09.725-05:00Does anyone know the history behind why we call th...Does anyone know the history behind why we call this Hoeffding's bound and not Bernstein's? Bernstein's paper was in the 1920s and seems to also have the result, at least according to what's on wiki: http://en.wikipedia.org/wiki/Bernstein_inequalities_(probability_theory)<br /><br />S.N.Bernstein, "On a modification of Chebyshevâ€™s inequality and of the error formula of Laplace" vol. 4, #5 (original publication: Ann. Sci. Inst. Sav. Ukraine, Sect. Math. 1, 1924)Jelaninoreply@blogger.com