tag:blogger.com,1999:blog-3722233.post113586087269936381..comments2021-12-01T13:41:42.544-06:00Comments on Computational Complexity: Year in ReviewLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-1136719704393922812006-01-08T05:28:00.000-06:002006-01-08T05:28:00.000-06:00Lance, many thanks for the so many pleasant hours ...Lance, many thanks for the so many pleasant hours i spent in front of your blog. Let me make a wish for 2006: I think our community deserves its own forum. Maybe you can add such a forum to your blog?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135898764253235992005-12-29T17:26:00.000-06:002005-12-29T17:26:00.000-06:00I will offer a vote for the ppad-hardness of 2-pla...I will offer a vote for the ppad-hardness of 2-player nash being surprising. for siva's sake, let me clarify "surprising":<BR/><BR/>It is a long-standing open problem that a significant fraction of people thought would be resolved with an algorithm finding equilibria in such games.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135890221321730902005-12-29T15:03:00.000-06:002005-12-29T15:03:00.000-06:00I second the suggestion that Lance be given the TC...I second the suggestion that Lance be given the <I>TCS blogger of the year</I> title.<BR/><BR/>Thanks<BR/>AmarAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135889881954089772005-12-29T14:58:00.000-06:002005-12-29T14:58:00.000-06:00What is your (and readers') take on the most surpr...What is your (and readers') take on the most surprising <EM>result</EM> of the year? That is, the most surprising theorem (proofs aside)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135881847923139992005-12-29T12:44:00.000-06:002005-12-29T12:44:00.000-06:00True, mathematicians distinguish proofs on the bas...True, mathematicians distinguish proofs on the basis you describe, which makes almost all of computer science 'elementary'. Obviously this is not a useful criterion for practitioners of complexity, nor do they use it this way.<BR/><BR/>The most obvious use of the term 'elementary proof' is to mean 'short proof', or, more strictly and recursively, 'short proof that doesn't have to invoke any results that don't yet have elementary proofs'.<BR/><BR/>I think the term also indicates that the techniques used in the proof are relatively familiar to most researchers. Thus, the most elementary proofs are those that are based on simulation techniques (and relativize). Somewhat less so are probabilistic arguments, then comes algebraic techniques.. if you've proved something that crucially uses topology or complex analysis towards answering questions basic to computational complexity (as opposed to showing NP-completeness of a topological problem, say), give yourself a cookie--that's probably a non-elementary proof.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135879143850195512005-12-29T11:59:00.000-06:002005-12-29T11:59:00.000-06:00And the award for "TCS Blogger of the year" goes t...And the award for "TCS Blogger of the year" goes to you Lance. Thanks.<BR/><BR/>The readers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135873014726932012005-12-29T10:16:00.000-06:002005-12-29T10:16:00.000-06:00Why do we call the originalPCP proof nonelementary...Why do we call the original<BR/>PCP proof nonelementary <BR/>and the new proof elementary?<BR/>If I understand correctly, non elementary means<BR/>involving complexity analysis, like the first<BR/>proof of prime number theorem. Elementary does not use complex analysis,<BR/>like Erdos-Selberg proof<BR/>of PNT. If this is true,<BR/>then both proofs of<BR/>PCP are elementary, right?Anonymousnoreply@blogger.com