What Is Theoretical Computer Science?

submited by

Style Pass

2024-10-18 06:30:05

I consider myself a computer science (CS) theoretician, but Wikipedia describes me as a “mathematician and computer scientist.”a So, what am I? To answer that question, we must consider theoretical computer science (TCS), which Wikipedia defines as “a subfield of computer science and mathematics that focuses on the abstract mathematical foundations of computation.”b I’d like to take issue with this definition.

In his lovely 2019 book, Mathematics and Computation,c 2023 ACM A.M. Turing Award recipient Avi Wigderson defines the theory of computation as “the study of the formal foundations of computer science and technology.” This is a very broad definition, but the scope of the book does not match that definition. It offers a very U.S.-centric view of TCS. As I have written elsewhere,d U.S. TCS has a quite narrower scope than European TCS, which I find unfortunate.

I believe that Avi has the right and broad definition for theoretical computer science; it is “the study of the formal foundations of computer science and technology.” In fact, if one browses 1970s proceedings of the ACM Symposium on the Theory of Computing (STOC) and the IEEE Symposium on Foundations of Computer Science (FOCS), one sees indeed a very broad conception of TCS. Only in the 1980s, with the proliferation of the so-called “satellite conferences,” dedicated to topics such as databases, program verification, and the like, did the scope of STOC and FOCS narrow, which led to a narrowing of how TCS is viewed in the U.S.