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.