2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Related but asking about simplicity of questions rather than topic: meta.cstheory.stackexchange.com/questions/17/scope-of-questions $\endgroup$ – Shane Aug 25 '10 at 13:28
  • 2
    $\begingroup$ If we need to clarify our scope, perhaps we could give examples of conferences whose topics are within the scope of this site. To give an example, "parallel and distributed computing" is vague and it clearly contains both lots of on-topic subareas and off-topic subareas. On the other hand, the kind of work that is presented at conferences like PODC, SPAA, DISC should be on-topic here. $\endgroup$ – Jukka Suomela Aug 25 '10 at 14:44
9
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So you don't think that certain of these areas would continue on MO? $\endgroup$ – Shane Aug 25 '10 at 14:25
  • 2
    $\begingroup$ there will surely be overlap, and I'm not in favor of killing areas that have MO elements. $\endgroup$ – Suresh Venkat Aug 25 '10 at 14:30
  • 1
    $\begingroup$ @Shane: Overlap with MO is fine, I think: we won't run into the troubles SOFU has. The point is that the two sites have different cultures, and will bring different expertise to bring on the same question. I'm not against the same question being asked in parallel, provided the questions are cross-referenced. $\endgroup$ – Charles Stewart Aug 26 '10 at 8:28
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .