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.

Improve this question
$\endgroup$
6
  • 8
    $\begingroup$ this should be a CW... $\endgroup$
    – Lev Reyzin ♦
    Commented Sep 17, 2010 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
    Commented Sep 17, 2010 at 16:29
  • $\begingroup$ Look at this list on meta, from SIGACT: meta.cstheory.stackexchange.com/questions/119/… $\endgroup$
    – Suresh Venkat
    Commented Sep 17, 2010 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
    Commented Sep 17, 2010 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
    Commented Sep 18, 2010 at 3:28

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I guess parallel algorithms disappeared to SPAA, PODC, DISC, IPDPS, ICDCS, ... $\endgroup$
    – Jukka Suomela
    Commented Sep 17, 2010 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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Sep 17, 2010 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
    Commented Apr 22, 2012 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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