5
$\begingroup$

I often want to give students a broad view of theoretical computer science, in the beginning of algorithms class or when advising a new student. It is hard for me to decide which sub-areas to talk about and how much emphasis to put on each of them.

Therefore, my question is: What are the main sub-areas of theoretical computer science and what is their relative "size"? Let's say the size is the number of researchers who work mostly in that area.

Of course the division into sub-areas is a clustering problem with no unique answer. I also don't expect people to have precise statistics for the size of each area, but some feeling of the relative sizes is already helpful.

$\endgroup$
  • 8
    $\begingroup$ this should be a CW... $\endgroup$ – Lev Reyzin Sep 17 '10 at 15:50
  • $\begingroup$ 1. Main subareas of theoretical computer science are listed on Wikipedia. Have you looked at it? en.wikipedia.org/wiki/… 2. I do not know about the “relative size,” but I do not think that it can be answered without being too subjective to be suitable on this site. $\endgroup$ – Tsuyoshi Ito Sep 17 '10 at 16:29
  • $\begingroup$ Look at this list on meta, from SIGACT: meta.cstheory.stackexchange.com/questions/119/… $\endgroup$ – Suresh Venkat Sep 17 '10 at 16:59
  • $\begingroup$ Tsuyoshi, thank you for the pointer. The list of sub-areas of tcs on wikipedia is: Mathematical logic, Automata theory, Number theory, Graph theory, Type theory, Category theory, Computational geometry, and Quantum computing theory. Wikipedia also lists algorithms and data structures as a separate area with 3 sub-areas: Computability theory, Computational complexity theory, and Cryptography. $\endgroup$ – Guilherme D. da Fonseca Sep 17 '10 at 17:06
  • 1
    $\begingroup$ I can't imagine how this question can be answered in its current form without being too subjective. It's not even clear to me what an acceptable answer to this question is. Should everyone just post what they think are the main sub-areas of TCS? $\endgroup$ – Robin Kothari Sep 18 '10 at 3:28
4
$\begingroup$

Also I wonder if 'size' is the right metric. that tends to vary as subfields come in and out of fashion. For example, a visitor from the 1980s would be very puzzled as to where all the parallel algorithms disappeared to. Someone attending SoCG in the last five years would think that we should call it the Symposium on Computational Topology :).

Maybe the best thing to do is to let the student browse proceedings from theory conferences to get a sense of what's in vogue RIGHT NOW, and emphasize that this answer will change over time.

$\endgroup$
  • 1
    $\begingroup$ I guess parallel algorithms disappeared to SPAA, PODC, DISC, IPDPS, ICDCS, ... $\endgroup$ – Jukka Suomela Sep 17 '10 at 18:54
2
$\begingroup$

If you look at:

http://arxiv.org/

you can see how they organize the different parts of Computer Science and also see the relative number of contributions that are being posted to the different parts.

$\endgroup$
  • 2
    $\begingroup$ I will comment that the arxiv classifications are not the best. merging data structures and algorithms is just confusing, for one thing. and algorithms itself is a very broad category, compared to (say) computational geometry. $\endgroup$ – Suresh Venkat Sep 17 '10 at 20:26
  • $\begingroup$ I feel like when people say algorithms, they're talking about the things that follow from the big CS developments in the 60's, basically CLRS and it's lineage. This doesn't really include computational geometry, mathematical programming, sampling methods (and associated theoretical machinery), machine learning methods, cryptography, highly mathematical graph theory, and a whole bunch of other things that involve algorithms; yet the distinction seems somewhat clear (though maybe I'm just ignorant of modern developments). $\endgroup$ – Elliot JJ Apr 22 '12 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.