<p><strong>Regarding topics</strong></p>

<p>There are different type of issues that may be considered
<em>theoretical</em> computer science. The important word here is
"<em>theoretical</em>" (as we all have some idea of what computer science
deals with). Understanding the word <em>theoretical</em> 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:
<em>theoretical</em> 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.</p>

<p><em>Theoretical</em> can be opposed to <em>practical</em>, which is how this knowledge
is used to actually run computing engines, to build systems, etc. I
can also be opposed to <em>applied</em> which is the use of this knowledge to
address problems in other fields of science and human activities.</p>

<p>But I doubt there are clear-cut boundaries.</p>

<p>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.</p>

<ul>
<li><p>one domain is <em>computability</em>, which studies what can be computed,
and how in a rather abstract sense: largely what is described in
Suresh Venkat's answer.</p></li>
<li><p>another is <em>algorithmics</em>, that finds effective means to compute
answers to specific problems, with specific
constraints. Computability is a theoretical context for algorithmics.</p></li>
<li><p><em>semantics</em> (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.</p></li>
<li><p>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 <a href="http://en.wikipedia.org/wiki/Hypercomputation">hypercomputation</a>.</p></li>
</ul>

<p><strong>Regarding specific activities</strong></p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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 <em>simpler</em> closure properties for a given family, and we
get "for free" a whole set of other properties.</p>

<p>Another important point is that <em>there is not such a clear-cut distinction
between theoretical, practical, or experimental work</em>. 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.</p>

<p>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.</p>

<p>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.</p>

<p>Two things often forgotten: ethics of science, and explaining it to
people.  Both are essential, and hard.</p>

CC BY-SA 3.0
2014-06-09T23:04:12.090Z
like the ref to [theory vs experiment](http://vzn1.wordpress.com/2014/02/14/great-moments-in-empiricalexperimental-mathtcs-research-breakthough-sat-induction-idea/) but actually there seems to be a fairly strict separation between theoretical/experimental work in TCS favoring/emphasizing the former at least on this site.... empirical work is not large in comparison & slowly becoming more accepted....
vzn
CC BY-SA 3.0
2014-06-06T13:04:26.607Z
2014-06-09T14:59:47.303Z
2014-06-09T14:59:47.303Z
babou
<p>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: </p>

<ul>
<li>what can we compute ? </li>
<li>how can we compute it ? </li>
<li>How fast ? </li>
<li>what happens when we have limited resources to compute ? </li>
<li>what are limits on what we can compute ? </li>
</ul>

<p>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. </p>

CC BY-SA 3.0
2015-01-09T14:45:37.347Z
This seem to me the key questions in "Theory A" (computability, complexity, algorithms), not "Theory B" (logics, semantics, programming language theory).
(See http://cstheory.stackexchange.com/q/1521/989 on the terminology).
Blaisorblade
CC BY-SA 3.0
2014-06-06T09:34:29.230Z
2014-06-06T09:34:29.230Z
Suresh Venkat
<p>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 &amp; may be helpful. they are more aimed at PhD student life &amp; CS oriented but most will carry to professor level research (other than teaching, but which also many Phds do). [&amp; in <em>some ways</em> 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.</p>

<ul>
<li><p><a href="https://people.cs.umass.edu/~emery/misc/how-to.pdf" rel="nofollow">How to do Research At the MIT AI Lab</a> "by a whole bunch of current, former, and honorary
MIT AI Lab graduate students" / 
David Chapman, Editor</p>

<blockquote>
  <p>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).</p>
</blockquote></li>
<li><p><a href="http://people.cs.umass.edu/~wallach/how_to_be_a_successful_phd_student.pdf" rel="nofollow">How to Be a Successful PhD Student (in Computer Science)</a> Mark Dredze (Johns Hopkins University),  Hanna M. Wallach (University of Massachusetts Amherst)</p></li>
</ul>

CC BY-SA 3.0
2014-06-11T16:33:04.113Z
also quite a bit of researcher daily life can be gleaned from some [computer science blogs](http://cstheory.stackexchange.com/questions/22191/what-cs-blogs-should-everyone-read) written with "inside looks"
vzn
CC BY-SA 3.0
2014-06-11T16:22:27.293Z
2014-06-11T16:27:27.417Z
2014-06-11T16:27:27.417Z
vzn
<p>I am trying to understand what is involved in theoretical computer science research. What do theoretical computer scientists do? </p>

<p>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?</p>

CC BY-SA 3.0
2014-06-06T08:57:21.233Z
"how do you spend your research time?" ... facing problems that I will probably never be able to solve :-) :-)
Marzio De Biasi
CC BY-SA 3.0
2014-06-06T09:32:10.970Z
That's like describing painting as "mixing paints, mounting a canvas, painting, and cleaning your instruments". In other words, it describes what it might look like to someone watching, but has no relation to what the field is about :)
Suresh Venkat
CC BY-SA 3.0
2014-06-06T10:24:29.097Z
Other activities: sport, hiking, cultural activities, and more
generally having a life. Doing other things helps your thinking (and
your health).
babou
CC BY-SA 3.0
2014-06-06T13:31:17.727Z
I think the question is not about the philosophy of TCS research or what makes you a better researcher, but really on what kind of concrete activities a TCS researcher does during working hours. Besides what already appears in the question, I would add preparing talks, giving talks, attending conferences, proofreading their own papers, reviewing papers of others.
Daniel Marx
CC BY-SA 3.0
2014-06-06T15:20:25.407Z
much research is oriented around [_open problems_](http://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science) or touching on near variants etc
vzn
CC BY-SA 3.0
2014-06-06T23:47:31.170Z
Thank you. I have some idea of the type of research questions you study. I want to know more about your daily activities. Researching in software engineering involves developing computer programs, running experiments, collecting and analysing data, ... I want to know what is involved in researching in theory. What's your typical workday like?
undergrad cs student
CC BY-SA 3.0
2014-06-09T23:01:59.750Z
re mtgs also dont forget [conferences/workshops](http://cstheory.stackexchange.com/questions/7900/list-of-tcs-conferences-and-workshops)
vzn
CC BY-SA 3.0
2014-06-11T20:10:58.180Z
It involves "...pounding your head against the wall for a long time...". Read more [Bob Tarjan interview](http://www.hpl.hp.com/news/2004/oct_dec/tarjan.html).
Pratik Deoghare
CC BY-SA 3.0
2014-06-12T01:11:33.443Z
See [my answer to a related question](http://academia.stackexchange.com/a/2221/65).
Jeffε
<soft-question><research-practice>
What does research in theoretical computer science involve?
undergrad cs student
# What does research in theoretical computer science involve?

(Asked by: username_0 on 2014-06-06)

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?

**Tags:** soft-question, research-practice

> **Comments:**
> **username_1**: "how do you spend your research time?" ... facing problems that I will probably never be able to solve :-) :-)  
> **username_2**: That's like describing painting as "mixing paints, mounting a canvas, painting, and cleaning your instruments". In other words, it describes what it might look like to someone watching, but has no relation to what the field is about :)  
> **username_3**: Other activities: sport, hiking, cultural activities, and more generally having a life. Doing other things helps your thinking (and your health).  
> **username_4**: I think the question is not about the philosophy of TCS research or what makes you a better researcher, but really on what kind of concrete activities a TCS researcher does during working hours. Besides what already appears in the question, I would add preparing talks, giving talks, attending conferences, proofreading their own papers, reviewing papers of others.  
> **username_5**: much research is oriented around [_open problems_](http://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science) or touching on near variants etc  
> **username_0**: Thank you. I have some idea of the type of research questions you study. I want to know more about your daily activities. Researching in software engineering involves developing computer programs, running experiments, collecting and analysing data, ... I want to know what is involved in researching in theory. What's your typical workday like?  
> **username_5**: re mtgs also dont forget [conferences/workshops](http://cstheory.stackexchange.com/questions/7900/list-of-tcs-conferences-and-workshops)  
> **username_6**: It involves "...pounding your head against the wall for a long time...". Read more [Bob Tarjan interview](http://www.hpl.hp.com/news/2004/oct_dec/tarjan.html).  
> **username_7**: See [my answer to a related question](http://academia.stackexchange.com/a/2221/65).  

---

## 3 answers

### Answer by username_3 on 2014-06-06. Score: 14

**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
  username_2'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](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_5**: like the ref to [theory vs experiment](http://username_51.wordpress.com/2014/02/14/great-moments-in-empiricalexperimental-mathtcs-research-breakthough-sat-induction-idea/) but actually there seems to be a fairly strict separation between theoretical/experimental work in TCS favoring/emphasizing the former at least on this site.... empirical work is not large in comparison & slowly becoming more accepted....  

---

### Answer by username_2 on 2014-06-06. Score: 8

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:

* what can we compute ?
* how can we compute it ?
* How fast ?
* what happens when we have limited resources to compute ?
* what are limits on what we can compute ?

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.

> **Comments:**
> **username_8**: This seem to me the key questions in "Theory A" (computability, complexity, algorithms), not "Theory B" (logics, semantics, programming language theory). (See http://cstheory.stackexchange.com/q/1521/989 on the terminology).  

---

### Answer by username_5 on 2014-06-11. Score: 4

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](https://people.cs.umass.edu/~emery/misc/how-to.pdf) "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)](http://people.cs.umass.edu/~wallach/how_to_be_a_successful_phd_student.pdf) Mark Dredze (Johns Hopkins University), Hanna M. Wallach (University of Massachusetts Amherst)

> **Comments:**
> **username_5**: also quite a bit of researcher daily life can be gleaned from some [computer science blogs](http://cstheory.stackexchange.com/questions/22191/what-cs-blogs-should-everyone-read) written with "inside looks"  

---

