We have often seen theorems proven multiple times in our field, because the result was proven on both sides of the iron curtain (e.g. Cook and Levin), sometimes it is just easier to prove a lemma then work through the literature, or we just simply didn't realize someone else had thought about the same problem. We have a considerable number of published work in our field and you cannot hope to know every "known" result, even in an area where you are considered an expert.
There is no ethical breech if you reprove someone else's theorem as long as you make good once you learn the result already existed. Although I have occasionally reproven theorems I had seen previously in talks or papers I've reviewed and that's just downright embarrassing.
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.
ReplyDeleteThis 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 implies the original theorem then one may be said to be reproving the same result, but that is not the point of the later work.
ReplyDeleteBy 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!
Varsha
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.
ReplyDeleteI still find it amazing that game-theorists in the 1950s were basically looking at the competitive analysis of randomized online algorithms!
For Varsha:
ReplyDelete1) Thank you for the encomiums
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.
Rakesh