Our domain scope, specifically defined

Question

There have been many independent questions about whether things are on/off-topic, but I think that we should be explicit at this point about our scope. The wikipedia article on TCS could provide a good starting point for discussion.

Wikipedia starts broadly (A):

The field of theoretical computer science is interpreted broadly so as to include algorithms, data structures, computational complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.

Then the core wikipedia list is (B):

• Mathematical logic
• Automata theory
• Number theory
• Graph theory
• Type theory
• Category theory
• Computational geometry
• Quantum computing theory

Another list taken from Challenges for Theoretical Computer Science defines it as covering (C):

• Cryptography and Security
• Combinatorial Algorithms
• Computational Geometry
• Parallel and Distributed Computing
• Complexity Classes
• Lower Bounds
• Logic, Semantics, and Programming Methodology
• Learning Theory
• Statistical Inference

I'm inclined to think that none of these are perfect. (A) is too broad, (B) includes some fields that may already be sufficiently served on MO, and (C) is close but has some things that don't seem to fit here (statistical inference?) and doesn't includes others (quantum computation).

I propose the following: we should put together a list of subfields that is appropriate for the site, give them unique tags, and then add them into our FAQ. This will reduce any lingering confusion.

Alternatively, we can let this be a community driven decision based on what is asked and accepted over time.

Answer 1

I'm inclined to go with the wikipedia definition from SIGACT:

The field of theoretical computer science is interpreted broadly so as to include algorithms, data structures, computational complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.

I think that last phrase--CS research with an "emphasis on mathematical technique and rigor"--is really the important part, and I would rather err on the side of including too much than too little. In particular, I think fields like machine learning should be allowed as long as the questions are appropriate. I don't see overlap with MO as a problem, especially since the emphasis is likely to be different.

Answer 2

How about all of these, with an 'including but not limited to...' phrasing. I think statistical inference is ok, upto a point btw.

Answer 3

I would address more specifically the overlap with MO of list B, for a few cases:

• Category theory
• Mathematical logic
• Type theory

These fields have a specific application to theoretical CS, especially to Programming Language Theory. So questions in these fields arising from CS would better fit here rather than on MO (I am myself a PhD student in Programming Languages).

• Graph theory

Here, I believe the difference of communities (with MO) leads to asking different questions - e.g., when defining a problem on graphs, mathematics often deals with existence theorems, while computer science wonders about the computability and complexity of answering such problems. But admittedly, this is probably a bit naive.

• Number theory

This is inappropriate, unless one means computational number theory.