tag:blogger.com,1999:blog-3722233.post113499915950798679..comments2023-06-08T07:53:14.980-05:00Comments on Computational Complexity: Favorite Theorems: First Decade RecapLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-1135066883658281842005-12-20T02:21:00.000-06:002005-12-20T02:21:00.000-06:00Closure of space under complement was already on L...Closure of space under complement was already on Lance's list for the 1985-1994 decade and computational zero-knowledge proofs also are in the wrong decade for the upcoming list.<BR/><BR/>Bryant's OBDD paper was 1986 as well.<BR/><BR/>Randomized computation in the form of Solovay-Strassen/Rabin-Miller primality testing and Schwartz-Zippel identity testing should not be excluded because they are 'algorithmic'. BPP and RP would be have been relatively boring classes without these algorithms to liven them up.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135034456491428062005-12-19T17:20:00.000-06:002005-12-19T17:20:00.000-06:00Let me throw in one more: Khachiyan's result and t...Let me throw in one more: Khachiyan's result and the ones following it (Karmarkar-Karp, Papadimitrou) for solving LP problems, and thereby solving a whole set of combinatorial problems. Made one more problem drop into the set of P (in a previously not thought of way).<BR/><BR/>Of course, it is Lance's favorite list!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135031785637408752005-12-19T16:36:00.000-06:002005-12-19T16:36:00.000-06:00Re: the last comment, just among the last 30 repor...Re: the last comment, just among the last 30 reports on ECCC, there are solutions to three major open problems, in coding theory, game theory and linear programming respectively. What is most encouraging is that these results appear on ECCC without consideration to artificial boundaries drawn by some people (for purely political reasons) between complexity, algorithms and other fields of theory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135030265311376242005-12-19T16:11:00.000-06:002005-12-19T16:11:00.000-06:00On a VERY DIFFERENT topic: It's worth noting that ...On a VERY DIFFERENT topic:<BR/> It's worth noting that the number of ECCC reports this year is at a record breaking 158. <BR/><BR/>Hint to Lance: a post on ECCC's contribution to disseminating complexity research :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135029140938636902005-12-19T15:52:00.000-06:002005-12-19T15:52:00.000-06:00To digress: The OBDD paper is the most cited pape...To digress:<BR/><BR/><EM> The OBDD paper is the most cited paper in computer science, according to Citeseer.<BR/></EM><BR/><BR/>That is true. But Citeseer does not handle well those CS papers that appear in the non-CS literature (as well as the citations from such papers). Based on Google Scholar, there is (an arguably CS) paper with higher citation count:<BR/><BR/>"Basic local alignment search tool"<BR/>� , W Gish, W Miller, EW Myers, DJ Lipman, DJ - J. Mol. Biol, 1990<BR/>Cited by 14181<BR/><BR/>compared to<BR/><BR/>"Graph-based algorithms for Boolean function manipulation"<BR/>RE Bryant� - IEEE Transactions on Computers, 1986 <BR/>Cited by 3511Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135027467177372412005-12-19T15:24:00.000-06:002005-12-19T15:24:00.000-06:00It seems a bit of a stretch to view the Diffie-Hel...It seems a bit of a stretch to view the Diffie-Hellman and RSA papers as being papers on <EM>complexity</EM>; in fact, I would barely call them theory papers (though I do not argue that they had huge impact and are seminal papers, nor that they influenced much later work in theory and complexity).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135025213771865312005-12-19T14:46:00.000-06:002005-12-19T14:46:00.000-06:00Yes, I agree. nice is "too simplistic and not too ...Yes, I agree. nice is "too simplistic and not too nice" word to describe theorems. Thanks!<BR/><BR/>Though It seems to me that UNION-FIND is not just algorithms. If we are talking just about the hardest problems in NP, then it does not fit in. OTOH, if we are talking about the theory of lower bounds of all problems in NP in general (not just the hardest ones), it does fit in.<BR/><BR/>AmarAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135018669488464722005-12-19T12:57:00.000-06:002005-12-19T12:57:00.000-06:00I think one other innovation from that decade was ...I think one other innovation from that decade was Ordered Binary Decision Diagrams (OBDDs). Though not exactly complexity theory, OBBDs and their algorithms have revolutionized other fields of computer science. The OBDD paper is the most cited paper in computer science, according to Citeseer.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135018103115292122005-12-19T12:48:00.000-06:002005-12-19T12:48:00.000-06:00Looking over my guest post on SURPRISING theorems,...Looking over my guest post on SURPRISING theorems,<BR/>and just taking those in 1974-1985 (the missing decade),<BR/>and taking out those in algorithms, here are 5 results<BR/>that should be in SOMEONES Top 10 of that Decade.<BR/>Are they in Lances?<BR/>We'll find out at some later time.<BR/><BR/>ALL are NICE theorems. The only reason they would NOT be in<BR/>is if someone found 6 nicer ones, so something has to go.<BR/><BR/>I did not include UNION-FIND since thats really algorithms,<BR/>though it is a nice theorem.<BR/><BR/><BR/>P vs NP cannot be solved by techniques that relatives (Baker, Gill, Solovay 1975).<BR/><BR/>Public Key Crypto (Diffie Helman, 1976, IEEE Trans Inform Theory, Rivest-Shamir-Adelman, 1978)<BR/><BR/>Permanent is #P complete. (Valiant 1979)<BR/><BR/>Bit commit --> SAT in ZK (Brassard,Crepeau FOCS86, Goldreich,Micali,Wigderson CRYPTO86, JACM91)<BR/><BR/>NSPACE(n) = coNSPACE(n). (1987-Szelepcsenyi-BEATCS, Immerman-1988-IEEECCC, SICOMP).<BR/><BR/>~ Bill GasarchGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135002861328216552005-12-19T08:34:00.000-06:002005-12-19T08:34:00.000-06:00Would really like to see Tarjan's ACKerman paper i...Would really like to see Tarjan's ACKerman paper in the missing list.<BR/><BR/>Amar<BR/>PS: Is voting allowed:)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135000990087937772005-12-19T08:03:00.000-06:002005-12-19T08:03:00.000-06:00Very nice list.Very nice list.ramakrishna uhttps://www.blogger.com/profile/06901176795841707101noreply@blogger.com