I'm currently starting on the university [computer science] and there we have lot of opportunities to begin with researching. Before finding this website, I had no intention to go on this way [I wanted to work with AI, probably game dev.], but now I can [or I need] to make a choice.

Can you convince me to join on this "world"? What "segments" I can follow? Is there anything about what kinds of topics a computer scientist or researcher works on?

  • 18
    $\begingroup$ We're honored that the site has already inspired you to think about theory! And you've come to the right place, if you want to know what a theoretical computer scientist works on... just keep reading and you'll find out! $\endgroup$ – Ryan Williams Sep 22 '10 at 5:06
  • 6
    $\begingroup$ This should be community wiki. $\endgroup$ – Dave Clarke Sep 22 '10 at 6:58
  • $\begingroup$ Just joined today and had same question... I did my engineering in Electronics engineering but while at college started to feel inclination towards CS... Never had formal introduction to Theory, but now I am glad I found this site... And @Júlio Souza thanks for asking this question. I am going to monitor this from today :) $\endgroup$ – Alan Turing Sep 24 '10 at 17:45
  • $\begingroup$ @supercooldave changed it to community wiki. $\endgroup$ – JulioC Sep 26 '10 at 5:51
  • $\begingroup$ Epilogue: JulioC became a software developer. $\endgroup$ – domotorp Oct 22 '19 at 18:45

I can relate my reasons as an undergraduate applying to TCS graduate programs this upcoming Winter (so little time left!).

  • There's the beauty. This isn't something I can explain (and have witnessed other mathematicians failing to explain). It's like "yellow." If you haven't seen it, I'm not sure I could communicate to you what it is. But since you've become interested in theory, I suppose maybe you do experience it.
  • There's universality. Universality beyond the Church-Turing Thesis. TCS at it's core investigates high level and low level phenomena in information - it's the "physics" of information. And since information is qualitatively atomic, information theory does have things to say about physics (my QM professor has specifically told me he loves information theory). All of this being said, it's somewhere between Pure Math and Engineering. It has the capability and flexibility to contribute directly to both, and to be contributed to directly by both. Still, it fights on its own frontier.
  • There's the scope. This was hinted at in the previous bullet. Informatics finds its way into many different applications - stuff everyone from the DHD to startups are interested in. You won't find yourself as starving for funding like Pure Mathematics. (You'll still always find yourself starving for funding.)
  • There's the challenge. Take a look at a list of open problems in Theoretical Computer Science (and pursue an understanding of them to the end of inquiry). They are very hard - here are some reasons why. We really don't understand TCS - most of our proofs boil down to mounting evidence. There's just so much work left to do!

Indeed whether you decide to go into research in theoretical computer science is a matter of choice. But even perusing the questions on this site (as you probably have done) hopefully gives you a sense of the breadth, scope an beauty of the field. I don't even know where to start in pointing you to sources you can read to appreciate the kind of work that theoreticians do, but there's one question on this very site that I think might interest you.

The question is:

Paul Erdos talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book.

If God had a similar book for algorithms, what algorithm(s) do you think would be a candidate(s)?

There are currently 64 answers to this question, covering algorithms for small problems, big problems, puzzles and deep mathematics. I strongly believe that if all you did was go through this list and read more about any of the algorithms that catches your eye, you'd learn a lot about what theoretical computer scientists do, and why we do it.

Good luck !


The reason many of us went into research is because we find pushing the boundaries of what is known both intellectually rewarding and enjoyable. Doing research also gives us almost unparalleled freedom to work on problems we find meaningful and interesting, and it keeps us constantly challenged (which we enjoy).

TCS (as opposed to other fields) is a mathematical study of computer science. You can work on the theory aspect of lots of different fields from distributed systems to machine learning. The choice among TCS and other fields in computer science depends on where your tastes and abilities lie. If your natural interests and abilities lie more in programming or system design than in mathematical analysis, then perhaps you shouldn't go into TCS. On the other hand, if your skills and interests lie more in the mathematical aspects, then you should consider TCS.

Also, you don't always have to choose one area over all others. Many people work on problems from both the theoretical and practical sides. This is common, for example, in machine learning, where we first design and analyze algorithms (often theory) and then test them in the real world (experimental design, applications, etc.).

A good way to figure out what you want to do is to take classes in many different areas, and perhaps try both industry and research in your summers. By the end of your studies, you will probably have a good idea of what you want to do.

  • $\begingroup$ I really like maths, but I love programming. Maybe I could find some way to work with both "sides" at the same time, like machine learning [which is in the AI area, right?]. On the next year, I'll apply to some classes on my university like AI and Algorithm Analysis that can help me. $\endgroup$ – JulioC Sep 23 '10 at 16:56
  • $\begingroup$ Machine learning (at least from my perspective) isn't a sub-area of AI, even though there is some overlap. Roughly speaking, AI focuses on solving problems that humans normally solve. Machine learning focuses on developing algorithms and systems that change behavior as they see data. So there is clearly overlap between the two fields, but they are far from the same. Machine learning clearly gives people the opportunity to do both theory and programming, but I am sure it's not the only subfield of CS for which it's true. $\endgroup$ – Lev Reyzin Sep 23 '10 at 17:47

Programming language theory is fun for young and old. It's applying logic to the real world. Come join the parade!!

More seriously, for me, programming language theory is interesting for the following reasons:

  • perceived impact on the real world: the extensive type system work in Haskell and other functional languages, originating from purely logical ideas (System F), significantly influences the development of languages such as Java (its horrible generics, closures) and Scala (the modern day where-theory-meets practice playground).

  • beauty: many of the tools employed in programming language theory are based on logic. Much of it stems from the Curry-Howard correspondence, which demonstrates a close connection between logical proof rules and typing rules for programming languages, and between cut-elimination in logic and evaluation in a programming language. Two recent beautiful examples of applications of logic in programming language research are the extensive work on separation logic in verification and the application of ideas of proof focusing to understanding programming language concepts such as evaluation order and pattern matching.

  • fun: you can do programming and theory at the same time, especially if you are formalising and verifying your theories using a proof assistant such as Coq.

  • and many more.


One of the main reasons why I find the theory of computation (“my” branch of theoretical computer science) fascinating and worth studying is the following one: it provides us with a way to investigate some deep (and sometimes puzzling) philosophical questions.

One of the founders of the theory of computation, Alan Turing, tried to pin down the meaning of “computing a function” for a human being equipped with a piece of paper, by giving a mathematical description of the process. I’m not the only one to think he was extremely successful, and Turing machines proved to be an accurate model of many other computing processes.

Now that we possess a class of mathematical objects describing computations, we can actually prove theorems about them, thus trying to uncover what can be computed, and how it can be computed; it immediately turned out that lots of perfectly legitimate functions cannot be computed at all, and that they can be classified according to a degree of uncomputability (some functions are just “more uncomputable” than others).

Some other guys, the first ones usually identified with Juris Hartmanis and Richard E. Stearns, tried to describe mathematically what it means for a function (resp., a problem) to be hard or easy to compute (resp., to solve). There are several complexity measures according to which the hardness of problems can be described; the most common one is just how much time we need to solve them. Alan Cobham and Jack Edmonds were quite successful in identifying a reasonable notion of “efficient computation”.

Within the computational complexity framework, we can now prove some results that are consistent with our intuitive notion of computation. My favourite example is the time hierarchy theorem: if we are given more time to compute, we can solve harder problems.

The central open problem of complexity theory, P vs NP, is just a formalisation of another philosophically significant question: is it really harder to solve a problem than to check if an alleged solution of it is indeed correct? I believe this question is worth asking, and answering, independently of its practical significance.

  • $\begingroup$ +1: liked :) ps: someone expressed similar opinions on Scott's blog. $\endgroup$ – Kaveh Dec 3 '10 at 12:49

We cannot "convince" you, since computer science is not mathematically better than AI or any other field. So, we cannot carry out a proof of its dominance! IMO, It is more a matter of taste than anything else.

  • 1
    $\begingroup$ I agree with you, but probably he wants to know why "you" (or everyone else here) chose this field. $\endgroup$ – M.S. Dousti Sep 22 '10 at 4:14
  • $\begingroup$ @Júlio Souza: In the title, it should be "theoretical" not "theorical". $\endgroup$ – M.S. Dousti Sep 22 '10 at 4:19
  • $\begingroup$ I don't want know if it's better, but I want know why you chose this field, as Sadeq said. $\endgroup$ – JulioC Sep 22 '10 at 4:33

It's hard to answer that question to a certainty, but there are a few things to keep in mind here.

If you make a career as a computer scientist, your job will probably involve not just processing and structuring data in a way that makes it useful and efficient to use, but also thinking about how and why what you are doing works, as well as in which bounds it operates (if for no other reason than to understand it enough to implement it). This is ESPECIALLY the case for AI/NLP/IR, which is VERY research-intensive, even if you are not in academia. In fact, going into AI pretty much guarantees that you will deal heavily in "theoretic" problems, and in fact it may be hard to find a job without that background. So that might be one compelling reason you would consider it.

Not only that, but it would probably be very hard to spend most of your life in any CS field, where you would have to maintain such intimate contact with such a delicate and capricious (and not to mention difficult) processes, while simultaneously maintaining no interest whatsoever in even the basics of why things work. In other words, I suppose you could glue together libraries for the rest of your life, but if that doesn't sound like your thing, you will have to have at least a passing acquaintance with the fundamentals of the problems you deal with.

While actively participating in TCS research is a question that probably only you can answer, a good starting point (IMO) is to start off with a view of the problems you're interested in looking at, and go from there. You may also not even have enough information to answer that question, so a better way to proceed might be to just see where your interests take you.

  • $\begingroup$ Thanks for the answer. I totally agree with your POV, work on something just doing it, without knowing why it works, how it works and if I could make it better is not something I want. I think I can try to keep my plans with AI [or something else, which is more like "pratical research"], but I'll keep trying to learn about other topics on TCS. $\endgroup$ – JulioC Sep 23 '10 at 16:49

What most intrigues me is the ability to apply the theory of computer science to other disciplines, especially biology and cell biology. If this notion intrigues you also, I'd suggest you take a look at the following: an essay by Jeannette Wing about the importance of Computational Thinking; and an NSF report about applying the Algorithmic Lens to other scientific disciplines.


Your Answer

