tag:blogger.com,1999:blog-3722233.post113910658133748214..comments2022-12-05T10:50:26.666-06:00Comments on Computational Complexity: Discovering the DiscoveredLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-1139352829451801332006-02-07T16:53:00.000-06:002006-02-07T16:53:00.000-06:00For Varsha:1) Thank you for the encomiums2) The si...For Varsha:<BR/><BR/>1) Thank you for the encomiums<BR/>2) The sixteen papers I listed (with one exception) prove either same theorem or a special case of that theorem. The exception is Blackwell who proves something more general. However as Avrim notes, there is a lot hidden in the constants, so in some cases we do learn something new from the later proofs.<BR/><BR/>RakeshAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139332361252705602006-02-07T11:12:00.000-06:002006-02-07T11:12:00.000-06:00For the problem of "combining expert advice" (you ...For the problem of "combining expert advice" (you have n strategies and want to do nearly as well as the best of them), the learning-theory approaches give you a bound of only O((log n) / epsilon^2) on the number of iterations you need to play until your average regret gets down to epsilon, whereas in Hannan's original algorithm it is O(n/epsilon^2). So if you think of "n" as a constant (like n=2 for the bit-guessing game) then there is no real difference, but if you think of n as huge (the motivation for the learning results) then it makes a difference. It's interesting though that some of the most recent work on structured settings (like Kalai-Vempala) go back to the Hannan *algorithm* but prove new things about it in a new context.<BR/><BR/>I still find it amazing that game-theorists in the 1950s were basically looking at the competitive analysis of randomized online algorithms!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139156912528199212006-02-05T10:28:00.000-06:002006-02-05T10:28:00.000-06:00This is a question for Rakesh Vohra (if he reads i...This is a question for Rakesh Vohra (if he reads it). To what extent are the sixteen papers he mentioned really proving the same theorem? After all, if one proves a result which <I>implies</I> the original theorem then one may be said to be reproving the same result, but that is not the <I>point</I> of the later work. <BR/><BR/>By the way, I agree wholeheartedly with the previous commenter: it was a truly wonderful talk. I can't think of many other talks I have enjoyed as much!<BR/><BR/>VarshaAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139111222250274622006-02-04T21:47:00.000-06:002006-02-04T21:47:00.000-06:00Rakesh's talk was excellent. On a subject relevant...Rakesh's talk was excellent. On a subject relevant to CS that we would otherwise be unlikely to hear about, presenting a good overview of the subject and highlighting the aspects that were of relevance for CS.Anonymousnoreply@blogger.com