Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I am trying to understand what is involved in theoretical computer science research. What do theoretical computer scientists do?
I know a significant time is spent on teaching, supervising graduate students, applying for funding, and departmental duties. Putting them aside how do you spend your research time? What are the major activities you typically do? I am guessing that you read papers, think, have meetings, and write documents. Are there any others?
Regarding topics
There are different type of issues that may be considered theoretical computer science. The important word here is "theoretical" (as we all have some idea of what computer science deals with). Understanding the word theoretical is not so obvious. For a long time I took it to mean mathematical, as opposed for example to "hacking". I learned better from people in linguistics: theoretical for them clearly does not meant mathematical, but based on a theory which may be somewhat informal (though it may be also mathematical), and is an organized body of knowledge and concepts that structure understanding of observable phenomena and hopefully allow some deductive and predictive use of the acquired knowledge. It also reduces the amount to learn and to teach by reducing the number of primitive concepts from which the rest can be deduced.
Theoretical can be opposed to practical, which is how this knowledge is used to actually run computing engines, to build systems, etc. I can also be opposed to applied which is the use of this knowledge to address problems in other fields of science and human activities.
But I doubt there are clear-cut boundaries.
This said, theoretical computers science covers diverse domains, and I will try to give some, while I am sure I forget others, and also that other people may disagree with this organization.
one domain is computability, which studies what can be computed, and how in a rather abstract sense: largely what is described in Suresh Venkat's answer.
another is algorithmics, that finds effective means to compute answers to specific problems, with specific constraints. Computability is a theoretical context for algorithmics.
semantics (for want of a better name), analyzes the conceptual organization of computational problems, and of algorithms, into higher level concepts, so as to factorize techniques that have proved useful and are often reused, such as the concept of subprogram,data-structures, modules, information hiding. It includes the development of mathematical tools that formalize adequately these concepts to allow high-level reasonning (Scott semantics for example). It also touches on the way this is expressed, thus on the separation and relation between syntax and semantics. Programming languages concepts are part of it (though language design is probably the pratical application of that knowledge). It can also include the relation between proof theory and computation theory, and the modern role of type systems.
another topic, which could develop more than it has so far, is the relation between computation and fundamental physics. For example. is there a relation between the limits on computation and the properties of the physical world, such as physical information density or the laws of thermodynamics. Quantum computing may improve a bit our computational prowess; could we hope for more? Some may dispute that this is still TCS, though there are TCS studies on hypercomputation.
Regarding specific activities
I am skipping the obvious activities required by academic life. or scientific life in industry: teaching, publishing, reviewing papers, writing grant applications, taking academic responsibilities, managing people, advising students or policy makers. But even then, there is no simple answer to your question. Here I am just sketching a few aspects that come to mind, but I am sure there is a lot more to be said. And I am not sure I am answering you. Some of the best scientists have written books about their work, and that may give you hints about scientific activities.
Researching in theory may involve a variety of things, depending on your skills and interests that vary a lot from scientist to scientist. It is somewhat hard to talk of it, since each person perceives more her own activity and interests than that of others. Most reasearch requires a wide knowledge, since interesting and really original results often comes from putting things in relation, or transferring a technique from one (sub)field to another, or getting different technical views of the same problem. So learning as much as you can in breadth as much as in depth is important. Remember that while you have the time and ability for it as a student, or as a junior faculty/scientist, both will be reduced later, because of responsibilities and life in general. Teaching what you do not specialize in may be a way to keep learning. On SE you can probably learn more by answering than by asking.
The kind of work people do can vary a lot, because people are fortunately very different, with a great variety of interests and technical abilities, thus complementing each other. Some people are problem solvers. They look at theoretical or practical questions raised by other people, or by themselves, and try to solve them, or get closer to a complete or partial solution. Other people will be better at structuring existing knowledge, and putting thing in relation, and then finding new questions to ask. Both are essential.
Finding simpler proofs of technical results, or simpler presentations of theories, or merging concepts is important. It generalizes results, reduces the numbers of things to learn, emphasizes the essential ideas and possibly brings new understanding. Since our learning time is limited, progress is possible only when we condense knowledge.
A simple example is the study of abstract families of formal languages. When language theory first developped, closure properties under various operation were proved again and again for each family of languages (regular, context-free, RE, ...), with ad hoc techniques depending on the family. Then it occurred that these closure properties had intrinsic relations independently of the concerned families, and they were studied as such. Today, we only have to check a few of the simpler closure properties for a given family, and we get "for free" a whole set of other properties.
Another important point is that there is not such a clear-cut distinction between theoretical, practical, or experimental work. A good theory may lead to the implementation of systems that can mechanize the resolution of problems. And it will take a good theoretician to implement such a system, with a mix of theoretical and practical work, including system implementation, or language design. Many examples come to mind, such as proof and/or program synthesis systems, specialized language for synchronous parallel systems, a restricted algorithmic language for which computational complexity can be systematically derived. Not only is it important to be able to produce such pratical systems, which make theoretical results more widely available and usable, but it is often very important for theoretician either to use proficiently these systems, if only to unload the now less creative parts of his work, or to contribute to the development and extension of these system.
Another aspect is to be able to compare theoretical approaches by pratical experimentation. Here, the issue is to compare different techniques to accomplish the same goal. Comparing implementations is often meaningless as their efficiency often depend on the programming language, or the programming skills of the implementor. But if they can be expressed all in a common theoretical framework, then it is sometimes possible to compare them experimentaly within that framework. Here, theory and practice support each other, as they often do in science. Pure theoretical analysis is not always easy to achieve. Furthermore, experimental analysis, when well conducted, can exhibit unexpected behavior that may motivate better theoretical analysis.
The world is not simple or clear-cut. That is why it can be fun, with room for all kinds of skills. Questionning your own knowledge, and answering questions of others, by whatever means.
Two things often forgotten: ethics of science, and explaining it to people. Both are essential, and hard.
In one sense, browsing this site will tell you the kinds of questions theoretical computer scientists think about (at a low level). At a very high level, theoretical computer scientist ask questions about the mathematical foundations of computation:
Starting from these questions, a whole host of other topics spring up, touching on applications areas, mathematics, other parts of computer science, and so on.
it occurred to me that 1sthand accounts might be helpful, but those seem to be somewhat rare in CS (as opposed to eg mathematics, biographical/ memoir-like writing etc). here are two online refs that address the question & may be helpful. they are more aimed at PhD student life & CS oriented but most will carry to professor level research (other than teaching, but which also many Phds do). [& in some ways professors can be seen as continually/repeatedly writing many "mini-" PhD theses (research papers) or in some cases "super-" Phd theses (books) over their careers.] there are also several decent books on the subject, will add some if you indicate they would be an acceptable answer for your question.
How to do Research At the MIT AI Lab "by a whole bunch of current, former, and honorary MIT AI Lab graduate students" / David Chapman, Editor
This document presumptuously purports to explain how to do research. We give heuristics that may be useful in picking up the specific skills needed for research (reading, writing, programming) and for understanding and enjoying the process itself (methodology, topic and advisor selection, and emotional factors).
How to Be a Successful PhD Student (in Computer Science) Mark Dredze (Johns Hopkins University), Hanna M. Wallach (University of Massachusetts Amherst)
