tag:blogger.com,1999:blog-3722233.post116103044791303541..comments2024-09-15T21:39:59.938-05:00Comments on Computational Complexity: Favorite Theorems: The Yao PrincipleLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-35601820762851487042024-04-03T14:54:27.785-05:002024-04-03T14:54:27.785-05:00It is also called Bakhvalov's trick since he u...It is also called Bakhvalov's trick since he used the same <br />idea earlier in a paper from 1959 on numerical integration. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82313334759055354502016-06-15T06:27:26.757-05:002016-06-15T06:27:26.757-05:00To I am what I am/Anonymous:
In fact, when Nash w...To I am what I am/Anonymous:<br /><br />In fact, when Nash went to von Neumann to present his theorem, he was dismissed with 'But that's just a fixed point theorem, it's trivial!'. That, however, won a Nobel.Teja yyyhttps://www.blogger.com/profile/04347059367465831890noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62229347187842083042009-09-16T04:46:09.883-05:002009-09-16T04:46:09.883-05:00To Anonymous,
its not that how easy to prove matte...To Anonymous,<br />its not that how easy to prove matters. It is how he modelled and observed. Like, Nash theorem is just application of kakatuni's fix point theorem. Credit goes for the modelling so that it is easy to prove and really works.I am what I amhttps://www.blogger.com/profile/10632729623999295377noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161097934222075342006-10-17T10:12:00.000-05:002006-10-17T10:12:00.000-05:00I am a famous complexity theorist and I approve th...I am a famous complexity theorist and I approve the previous message.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161062133385786772006-10-17T00:15:00.000-05:002006-10-17T00:15:00.000-05:00To anonymous:As Lance said "Andrew Yao observed......To anonymous:<BR/><BR/>As Lance said "Andrew Yao observed..."<BR/><BR/>Even though the result is trivial to prove, it is amazingly important and useful.<BR/><BR/>I believe this is why Yao gets so much credit for it.<BR/><BR/>(I am just a student. Some famous complexity theorist should back me up..)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161060276811298522006-10-16T23:44:00.000-05:002006-10-16T23:44:00.000-05:00This is regularly referred to as Yao's principle, ...This is regularly referred to as Yao's principle, and hailed as a great result. What I never understood was, is this -really- more than an application of Von Neumann's minimax theorem? It seems like a corollary od Von Neumman's theorem, that gets huge amounts of credit.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161040419968589872006-10-16T18:13:00.000-05:002006-10-16T18:13:00.000-05:00One of my favorite as well. I would add that this ...One of my favorite as well. I would add that this is very easy to use: instead of finding a single worst case (say, for a fixed size of input), you just have to find a bunch of those "worst cases", forming a distribution large enough that no algorithm can take advantage of it. Typically, taking all the instances which are the worst case of some deterministic algorithm...dothttps://www.blogger.com/profile/14825435867493579983noreply@blogger.com