Moshe Vardi wrote a short interesting essay “What is theoretical computer science?” (It followed by interesting posts on Facebook.) Moshe argues that
Thinking of theoretical computer science (TCS) as a branch of mathematics is harmful to the discipline.
I personally do not regard TCS as part of mathematics and I also don’t think that thinking of TCS as part of mathematics is harmful. Certainly there are parts of TCS that are also parts of mathematics as well. (I will try to add a schematic Venn-diagram a bit later.)
Update: Moshe Vardi gave me pointers to two related works: a) The paper FPRAS Approximation of the Matrix Permanent in Practice by James E. Newman, Moshe Y. Vardi argues that the constants in the “rapid mixing” algorithms for approximating permanents are too large to be realistic (related to item 10 below). b) The 2003 paper: Random 3-SAT the plot thickens describes experiments with SAT solvers on random 3-SATs.
Here are some unorganized quotes from the essay, my thoughts and related links.
- Theory and practice in TCS; my ICM18 paper. Moshe raises interesting issues about the interface between theory and practice in computer science and more broadly in Science and Engineering. This is a topic that greatly interests me and I devoted my ICM18 paper Three puzzles on mathematics, computations, and games, to three examples: linear programming, voting and games, and quantum computation.
- Aesthetic values as a primary motivation. Moshe advises to remember the warning of John von Neuman regarding the danger of mathematics driven solely by internal esthetics: “There is a grave danger that the subject will develop along the line of least resistance.” (See here for the full quote of von Neuman). Personally, I don’t see alternatives to internal aesthetics as a major driving force on all scales for mathematics.
- Physics inspiration. Moshe writes: “As computer scientists, we should look for inspiration from physics rather than from mathematics. Theoretical physics is highly mathematical, but it aims to explain and predict the real world. Theories that fail at this “explain/predict” task would ultimately be discarded. Analogously, I’d argue that the role of TCS is to explain/predict real-life computing.”
- Physics heuristic methods. Theoretical physics is characterized by powerful non-rigorous mathematical methods that give amazing predictions. These predictions are quite often confirmed and sometimes refuted. Such methods had some influence for algorithms and theoretical computer science but so far their influence has been limited. One very nice area of applications is the study of algorithms for random SAT problems. Here is a famous 2002 paper Analytic and algorithmic solution of random satisfiability problems by Mézard, Parisi, and Zecchina.
- SAT solvers. Moshe writes: “Over the past 30 years, however, we have made tremendous progress in SAT solving, which is today an industrial reality. NP-completeness theory, however, does not explain or predict the unreasonable effectiveness of SAT solvers.” In my view it is a great problem to understand when and why SAT solvers work. Probably mathematical ideas would be required to study this problem (but everything will go; in my three puzzles paper I suggested the gradual understanding over seven decades of the success of the simplex algorithm as a sort of role model for understanding the success of SAT solvers).
- Theory and practice: what is a proof? We talked about the practice and theory for proving mathematical theorems in this (sort of) debate between me and Avi Wigderson, and in several other posts (I,II,III).
- The very old debate: Karp’s committee vs. Wigderson & Goldreich. There was a related very interesting debate almost thirty years ago that is discussed in this blog post over the blog Computational Complexity (CC) that present the two positions as follows:
(Karp’s committee:) 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 and Avi’s view:) 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.
- Koblitz vs. Goldreich: In the context of Cryptography there was an interesting Koblitz-Goldreich debate, see this post from CC. Cryptography (including cryptanalysis) is a great subject, and I have a long term plan to write about it over here.
- The European “Theory A” and “Theory B”. Moshe mentioned that in Europe there are two types of “theoretical computer science” (“Theory A” and “Theory B”). I always found these different possibilities for a scientific theory of computer science quite exciting. Actually, some advances in linear programming (mentioned in my paper quoted above) grew from progress in both “Theory A” and “Theory B”.
- Computing volume in high dimensions. (This is a problem I heard from Moshe a decade ago.) Two of the greatest achievements in the theory of algorithms are the polynomial time algorithms for computing volume in high dimensions (Dyer, Friese, Kannan) and for approximating permanents of nonnegative matrices (Jerrum, Sinclair, Vigoda). Let me mention that the current spectacular world record for volume computations is steps by Ben Cousins and Santosh Vempala. The question to be asked is: are there practically good algorithms for these tasks?
- Randomness, statistics, and derandomization. A good place to check theory vs. practice is in the context of randomization. What are the TCS notions of “randomness” and how do they compare in theory and in practice with notions of randomness from probability theory and from statistics? How practical is the theory of “derandomization?”
Moshe’s article is part of the opinion section of the Communication ACM, where Moshe has a regular column. Let me also mention the European counterpart “The Bulletin of the European association of Theoretical Computer Science”.
A schematic Venn diagram of TCS, CS, Mathematics and other fields. Of course, every field represented here by a circle is by itself a complex fractal-like object. Avi Wigderson’s lovely book “Mathematics and Computation” gives a great description of some mathematical areas of TCS with a special chapter on connections between TCS and mathematics and another chapter on connections between TCS and other sciences. See also this post.