tag:blogger.com,1999:blog-3722233.post1733567208294013592..comments2024-03-18T23:13:09.570-05:00Comments on Computational Complexity: Karp v Wigderson 20 Years LaterLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-3722233.post-71669405531145739032016-06-30T09:44:17.326-05:002016-06-30T09:44:17.326-05:00As others have mentioned, both sides had a point, ...As others have mentioned, both sides had a point, and resolved their differences in the final report. <br /><br />The younger readers of the blog may not know, but 10-11 years ago Avi and Dick collaborated (along with a few others) to convince NSF to increase funding for theory. Both have been recognized by the distinguished service award to the field<br />(for this and other contributions). Sanjeev Arorahttps://www.blogger.com/profile/10896480884587733715noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5393711953186923722016-06-18T23:03:49.892-05:002016-06-18T23:03:49.892-05:00I think you misunderstood what aspect of the debat...I think you misunderstood what aspect of the debate I found (and find) misguided. And perhaps the word ``misguided'' was not what I meant, as much as ``lost opportunity''. What I believe is factually incorrect about the core theory vs. applied theory debate is that it assumes that the two aspects of theory are in any sense in opposition, whereas I believe that they are synergetic. Great core theory feeds techniques and models to applied theory and leads to great applied theory, and great applied theory introduces new problems that feed and expand core theory. Neither position paper (to my recollection) really captured this synergy, which is a shame. And Lance's blog post seemed to continue to frame the issue as one vs the other, rather than let's have more of both, please! <br /><br />Let me give some examples of what I mean. One example is the work Mike Luby just won the Kanellakis Prize for. That work was appearing in STOC/FOCS in 1994, and Luby was Karp's former student and current colleague. It was applying ideas from core theory to a real application, video streaming (a bit ahead of its time) and Luby was already thinking in terms of patents, and would eventually form his own company. This is work that drew on and contributed to theory, was started in FOCS/STOC papers, but was always motivated by concrete applications.<br /><br />The practice oriented provable security movement spearheaded by Bellare and Rogaway (and many others) was also picking up momentum at this time. This drew on but refined the models of theoretical cryptography but was motivated by making them more relevant to applied cryptrography. The movement then greatly enriched the scope of theoretical crypto. <br /><br />A third example is the Goldreich-Levin algorithm, for finding the large Fourrier coefficients. Originally, (as far as I know) it was motivated by entirely theoretical concerns, being used in a proof of correctness of a cryptographic construction and never intended to be implemented. But soon Kushelevitz and Mansoor were using the algorithm in learning theory (although maybe they didn't realize that's what they were doing). And just recently, the algorithm was adapted into the Sparse Fast Fourrier Transform, and has new applications in many areas of signal processing. <br /><br />Why didn't either paper brag about these connections being made? Karp et al paper seemingly lamented their non-existence (when they were happening right under the author's noses, and other connections were being made by the authors of the report!) whereas the Goldreich-Wigderson championed pure theory on esthetic grounds when it could have also championed it on the grounds of practicality. Anonymoushttps://www.blogger.com/profile/18394636887484222063noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9623234601430508092016-06-18T05:20:19.533-05:002016-06-18T05:20:19.533-05:00Suresh, thanks for mentioning some of the areas in...Suresh, thanks for mentioning some of the areas in which Volume B is having impact in the practice of computing. (In passing, Avi also mentioned verification tools in his <a href="http://blog.computationalcomplexity.org/2016/06/the-relevance-of-tcs.html" rel="nofollow">post</a> and "Anonymous 1:57 AM, June 17, 2016" also pointed out areas in which Volume B theory is having an impact on the practice of computing.) As three sample exhibits, let me mention, in no particular order:<br /><br />1. The work on Separation Logic that led to the development of the static analyzer <a href="http://fbinfer.com/" rel="nofollow">Infer</a>, which today checks every line of app code developed at Facebook. A related body of theoretical work on the development of Concurrent Separation Logic by Stephen Brookes and Peter O'Hearn has been awarded this year's Gödel Prize. <br /><br />2. The <a href="http://compcert.inria.fr/compcert-C.html" rel="nofollow">CompCert C compiler</a> is formally verified, using machine-assisted mathematical proofs, to be exempt from miscompilation issues. In other words, the executable code it produces is proved to behave exactly as specified by the semantics of the source C program.<br /><br />3. The model of timed automata, initially proposed by Rajeev Alur and David Dill, is at the core of industrial-strength verification tools that are actually used in checking real-time systems and to synthesize plans, schedules and control programs that actually run daily in embedded systems. This work receives the first Alonzo Church Prize for outstanding contributions to logic and computation. (See <a href="http://siglog.hosting.acm.org/wp-content/uploads/2016/05/church16.pdf" rel="nofollow">here</a>.) It has also had substantial impact in the control theory community.<br /><br />These are just three samples of a large body of theoretical work that is having impact on the practice of computing and is generating increasing interest. <br /><br />As Dino Distefano from Facebook and Queen Mary College said in an invited talk at a workshop I recently co-organized in Reykjavik. The journey is only 1% done. <br /><br /><br />Luca Acetohttps://www.blogger.com/profile/01092671728833265127noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6515377780151956582016-06-17T14:48:34.286-05:002016-06-17T14:48:34.286-05:00I think TCSs strength is in ideas, not implementat...I think TCSs strength is in ideas, not implementations. Sure, we can imagine a world where we not only generate ideas but also see them through to implementation. But that does not mean that our ideas have not been successful. I think it is better to not tout things like Apple doing differential privacy when the details are not clear.Chandrahttps://www.blogger.com/profile/00057069075567569157noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16945421306655831212016-06-17T14:23:11.426-05:002016-06-17T14:23:11.426-05:00It's not clear that apple is integrating diffe...It's not clear that apple is integrating differential privacy (other than the term for PR).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65141724644381195052016-06-17T12:20:10.206-05:002016-06-17T12:20:10.206-05:00Volume B theory is not doing too shabbily, if you ...Volume B theory is not doing too shabbily, if you look at the massive growth of interest in verifiable software, as well as all the interest in type theory, PL and automatic generation of code. And I think it's interesting that we're having this discussion literally two days after Apple decides to integrate differential privacy into its offerings. Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7795276729700828752016-06-17T03:26:15.766-05:002016-06-17T03:26:15.766-05:00I agree with the point of view expressed by Lance....I agree with the point of view expressed by Lance. It has been a golden age for computing but theory is less central and fundamental than it could have been. Volume A Theory has largely gone the way of Volume B Theory. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37198761350460116342016-06-17T02:57:22.658-05:002016-06-17T02:57:22.658-05:00In general, I'd rather people read the texts b...In general, I'd rather people read the texts before stating opinions regarding them. This is a main reason that I usually refrain from BLOGs. <br /><br />I disagree with Russell who thinks (and claims to have thought) that the debate was misguided. The fact that connections to the rest of CS were made much before 1995 and were continuously made at that time was known to all, and was stated explicitly and loudly in my essay with Avi. The debate was on proportions, and in particular referred to the recommendation of the Aho et al report (i.e., the report of the committee chaired by Karp) that TCS *redirects* itself and reduces the amount of "pure" (intristicly-oriented) research so to make room for more technological transfer. Let me stress that we were not "against applications" per se, but rather against *mandating* applications (let alone immediate and/or direct ones).<br /><br />In addition, and maybe more importantly, there was a gap between the implicit messages of the two texts. While acknowledging the contributions of TCS, the text of Aho et al reads as gloomy wrt the (past and) present achievements and alerting wrt future. In contrast, our essay celebrates the achievements of TCS and was read as uplifting and optimistic. In retrospect, I think this was its most important aspect. <br /><br />We did not "win" the debate, but the mere fact that there was a debate and the perspective of the Aho et al report was contested was important. Of course, one should not overestimate the importance of this fact, but I would not dismiss it as insignificant either. <br /><br /><br />Side comments:<br /><br />1. I don't like framing this as Karp-vs-Wigderson, as if it was some personal issue. Needless to say, it was not. As always, a personalization is catchy and may increase readership, but does not serve the interests of a debate.<br /><br />2. The joke "Why not start with the implementation" was made by Juris Hartmanis.<br /><br />(Oded Goldreich)Unknownhttps://www.blogger.com/profile/14949903633532114035noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21024663131848911312016-06-17T00:57:32.484-05:002016-06-17T00:57:32.484-05:00I would add two more topics that are missed in pre...I would add two more topics that are missed in previous comments: distributed computing and programming languages/type theory. Both of them are the foundations of the current distributed systems and programming language. The amount of attention that a functional programming language like Haskell is getting from ordinary programmers is amazing, I am amazed by the number of programmers and software developers who know or want to know about monads. On distributed computing front, Lynch's book is still the reference taught in systems community (os/networks/...) Algorithms lie Paxos are the foundation behind Google's Chubby and Apache Zookeeper without them none of the cloud services would be possible. Research in shared-memory is picking up again.<br /><br />I think your post is too much complexity theory centeric. Theoretical computer science is not just complexity theory. The criticism might be valid about complexity theory but not other areas in theoretical computer science. Maybe also learning theory.<br /><br />A big problem for interdisciplinary work with other areas is the language barrier. We need researchers from more applied side that understand the language of theory and researchers from theory side that understand their language. This probably needs a systematic approach to fix, maybe courses that forces theory students and non-theory students to partner and work together.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49504494348286581792016-06-16T23:26:39.778-05:002016-06-16T23:26:39.778-05:00@Anonymous 7:48pm 6/16/16: The question is whether...@Anonymous 7:48pm 6/16/16: The question is whether theory has really had such a large impact on those fields, or whether we theoreticians just like to *think* that it has. Ask people who work in those fields how much of a contribution STOC/FOCS-style theoretical computer science has made to their field, and see what they say. (I would say streaming/sublinear and quantum are actually just *part* of "Theory A," rather than other fields to which theory has contributed, so I'm really referring to the other elements in your list. Coding theory is borderline, depending on which parts of it you're talking about.) <br /><br />That being said, it may be that we are a victim of our own success. Much like philosophy in the 19th century ultimately led to most branches of science that exist today - yet most sciences today would say that they gain little from philosophy - perhaps theoretical computer science is the engine that spawned a thousand subfields, but once those subfields became independent they may no longer feel they are gaining much from the core theory community.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19817339787400961692016-06-16T18:48:30.942-05:002016-06-16T18:48:30.942-05:00I concur with James that this post is out of touch...I concur with James that this post is out of touch with the impact of theory on CS and beyond ranging from crypto/security, algorithms/optimization, ML, coding theory, streaming/sub-linear, auctions/agt, graph theory, quantum .... Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35632523805847650352016-06-16T18:02:27.879-05:002016-06-16T18:02:27.879-05:00Theory was already moving quite rapidly into makin...<i> Theory was already moving quite rapidly into making connections with other areas of CS. </i><br /><br />Theoreticians were doing so. The main conference venues, i.e. STOC and FOCS not so much. Hence the tension and debate. SODA arose from this tension and in my opinion it was a good fifteen years until those venues became truly receptive to the current diversity of topics. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70559707607991209212016-06-16T17:12:24.518-05:002016-06-16T17:12:24.518-05:00I feel like this post could have been written in 1...I feel like this post could have been written in 1995. The TCS world you describe feels very different from the one I inhabit. For lack of time at the moment, my comment admittedly contains little in the way of content, but this pessimistic(?) and isolationist view of the field feels foreign to me.Anonymoushttps://www.blogger.com/profile/05011711575259782857noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47951358795584066182016-06-16T15:29:29.276-05:002016-06-16T15:29:29.276-05:00I have the same opinion now as I did then: it was ...I have the same opinion now as I did then: it was a misguided debate. Theory was already moving quite rapidly into making connections with other areas of CS. It should have been sold as a success story, where core theory is the engine producing results that impact other fields, not as a field in crisis or in denial. Fortunately, if you look at what the debate lead to, it did lead to exactly this consensus, with groups such as Theory Matters showing that both sides cared more about the health of the area than about winning the argument. It's been a great 20 years for theory, both in terms of relevance and progress on our core questions, and we have even done relatively well in funding (at least compared to 1995). Outreach to other areas includes mathematics as well as computation economics. Both sides have done their part to keep theory strong. <br /><br />Are we the main drivers of the Internet economy? No, but considering our size and funding level, I think we punch above our weight class in terms of contributions. Anonymoushttps://www.blogger.com/profile/18394636887484222063noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62567139361186293392016-06-16T15:12:12.085-05:002016-06-16T15:12:12.085-05:00This seems a pretty narrow view of what has gone o...This seems a pretty narrow view of what has gone on in the last 20 years and the technologies based on theoretical ideas that have flourished. (A look at some of those Kanellakis prize winners would have been a start.) <br /><br />To me, in that debate both sides were right and both sides were wrong because neither side really anticipated the importance (and the array of new ways of thinking about fundamental problems) that the web and internet would almost immediately bring to theory. <br /><br />Also, on the industry side, I am not sure what you are remembering that was so great about the mid 1990's. Theory jobs were largely in Bell Labs' children; places like IBM were retrenching, with many of their researchers moving to academia and few new PhDs getting jobs. Microsoft had not even started a research lab. Even the pool of postdoc positions had shrunk and was much lower than it is today. Before the ill-chosen closure of MSR-SVC I think that your view of current industry theory jobs would not have been so negative even with Yahoo's troubles. (It is quite ironic that Apple just made a big splash announcing technology that came out of theory research in that lab.) Paul Beamehttps://www.cs.washington.edu/people/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61513162609665082892016-06-16T11:56:08.831-05:002016-06-16T11:56:08.831-05:00So, with the perspective of 20 years, who was righ...So, with the perspective of 20 years, who was right? <br /><br />Some parts of theory did well, it seems, by hooking up quite nicely with various application areas such as The Internet, Machine Learning, Quantum Information, or Game Theory.Anonymousnoreply@blogger.com