In order for TOC to prosper in the coming years, it is essential to strengthen our communication with the rest of computer science and with other disciplines, and to increase our impact on key application areas.Oded Goldreich and Avi Wigderson put together a competing report, Theory of Computing: A Scientific Perspective that focuses on theory as a scientific discipline.
In order for TOC to prosper in the coming years, it is essential that Theoretical Computer Scientists concentrate their research efforts in Theory of Computing and that they enjoy the freedom to do so.There was a lively discussion at the business meeting, with Karp and Christos Papadimitriou on one side, with Goldreich and Wigderson on the other. I remember one exchange where one side said that the people who implement an algorithm should get as much credit as those who developed it. Avi, I believe, said he'd like to see the implementer go first.
So what has transpired in the last two decades. The theory and community has not withered and died, the field continues to produce great results and attract many a strong student. On the other hand the theory community has not had the growth we've seen in other CS areas, particularly in the recent university expansion. Industrial research in core theory, which had its highs in the 90's, has dwindled to a small number of researchers in a few companies. Foundation research has helped some, IAS now has a faculty position in theoretical CS, the Simons Foundation funds some faculty and recently started an institute in Berkeley and the Clay Mathematics Institute has given the field a considerate boost by naming the P v NP problem as one of their millennial challenges.
The main core theory conferences, STOC, FOCS, SODA, Complexity and others have continued to focus on theorems and proofs. Rarely do the research in these papers affect real-world computing. The theory community has not played a major role in the growth of machine learning and has left real-world optimization to the operations research community.
We have seen some other developments making some progress in connecting theory to applications.
- 1996 saw the first Kanellakis Prize to honor "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing"
- Some companies, most notably Akamai, have come out of the theory community and helped shape real-world computing.
- We have seen new research communities in EC and Quantum Computing that connect with economists and physicists.
- The NSF now has a program Algorithms in the Field that connects theorists with applied computer scientists.
- Some theory topics like differential privacy have entered the mainstream discussion.
We live in a golden age of computer science and computing research is transforming society as we know it. Do we view ourselves as a scientific discipline divorced from these changes, or should theory play a major role? This is a discussion and debate the theory community should continue to have.
So, with the perspective of 20 years, who was right?
ReplyDeleteSome 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.
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.)
ReplyDeleteTo 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.
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.)
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.
ReplyDeleteAre 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.
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.
ReplyDeleteTheory was already moving quite rapidly into making connections with other areas of CS.
ReplyDeleteTheoreticians 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.
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 ....
ReplyDelete@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.)
ReplyDeleteThat 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.
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.
ReplyDeleteI 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.
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.
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.
ReplyDeleteI 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).
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.
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.
Side comments:
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.
2. The joke "Why not start with the implementation" was made by Juris Hartmanis.
(Oded Goldreich)
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!
DeleteLet 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.
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.
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.
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.
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.
ReplyDeleteVolume 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.
DeleteIt's not clear that apple is integrating differential privacy (other than the term for PR).
DeleteI 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.
DeleteSuresh, 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 post 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:
ReplyDelete1. The work on Separation Logic that led to the development of the static analyzer Infer, 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.
2. The CompCert C compiler 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.
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 here.) It has also had substantial impact in the control theory community.
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.
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.
As others have mentioned, both sides had a point, and resolved their differences in the final report.
ReplyDeleteThe 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
(for this and other contributions).