Tuesday, June 28, 2005

Defining Theory

Theory Matters points to a definition of Theoretical Computer Science given on the SIGACT Home Page.
The field of theoretical computer science is interpreted broadly so as to include algorithms, data structures, 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.
This definition first appeared in the December 1997 SIGACT News with a slightly different order and missing quantum computation and automata theory.

I dislike these "laundry list" definitions. They both tend to overcompensate by listing too many areas (e.g. "the study of randomness" is really subsumed by the other areas) and failure to capture all the areas we study (e.g. electronic commerce). Such lists cannot remain stable over time and need constant updating. We find it hard to delist any areas even if we should.

Most importantly laundry lists don't capture the spirit of a field. If we really wish to sell our field properly we need to start with a clear definition. Here is a suggestion.

Theoretical Computer Science is the formal analysis of efficient computation.
Simplicity should beat complexity every time.


  1. I think that formal analysis of efficient computation is more complexity theory than TCS as a whole and suggest the following alternative: TCS is the formal analysis of computation.

  2. Lance's proposed definition excludes all that is done in Theory B and possibly more. I suggest
    "Theoretical Computer Science is mathematical modeling and analysis of computation."

  3. I don't have a better definition right now, but I would point out that all the definitions suggested so far don't really capture most work in cryptography.

  4. How about the _design_ of algorithms or information theory or kolmogorov complexity or crypto? Building upon the previous two, while still trying to avoid a laundry list:

    "Theoretical Computer Science is the formal modeling, analysis and design of computation and information".

  5. But you are certainly not "designing" the information, so the above is misleading.

    My suggestion:

    Theoretical computer science is the formal modeling and analysis of the processing and transmission of information.

  6. We lost the design there. Also the part of transmission we care about it is capture by processing So let's try that again:

    "Theoretical computer science is the formal modeling, design and analysis of the processing of information."

  7. I don't think you can delete the "transmission of information" without substituting something else, because I don't see how "processing of information" covers, for example, crypto.

    Transmission of information was meant to cover the fact that theory is about communication, which is not implied by just saying processing.

  8. Is the formal definition of the field so important? If the main goal of a formal definition is to give the newcomer a taste
    of what goes on in the field, then in my opinion, an example-oriented approach (more along the lines of the laundry-list definition) is more appropriate.

    The laundry-list need not be comprehensive. Instead it is merely indicative of the kind of research that goes on in the field.

  9. How about "Theoretical computer science develops and applies mathematical methods for the systematic modeling, analysis, and solution of computational tasks"? This would take into account that theory covers not only 'internal' topics (as suggested by the "analysis of computation/information processing" definition), but is also sometimes applied to understand and develop tools for 'external' areas that have a computational character (such as e-commerce, comp. bio., networks etc.)

  10. I think the best so far is TCS is the formal analysis of computation. You don't have to mention "modeling" because that's a prerequisite of "formal analysis". It does capture crypto since crypto is based on what can and can't be computed efficiently. It also captures design of algorithms, since "analysis of computation" can include not only what can be computed, but also how it can be done efficiently. It would also be OK to substitute "processing of information" for "computation"; these appear synonymous to me.

    There still might be some missing areas: for example the question of whether one metric space embeds into another with constant distortion does not seem to involve any computation, although it might be answered using computational tools. But turning things around, I can't think of anything that falls under the above definition that isn't TCS.

  11. How about
    "TCS is the study of
    the foundational aspects of computation, information and
    related mathematics".

  12. begin to define TCS: lance saz: "Theoretical Computer Science is the formal analysis of efficient computation"

    an interesting analysis is always formal. plonk and redefine as "Theoretical Computer Science is the analysis of efficient computation"

    of course, a computation of interest is always efficient. plonk and redefine as "Theoretical Computer Science is the analysis of computation"

    of course, we analyse computation, not do it. plonk and redefine as "Theoretical Computer Science is computation"

    of course we study computation, not do it. plonk and redefine as "Theoretical Computer Science is ... "

    oh there is nothing in the definition!! let me add something to describe TCS. "Theoretical Computer Science is having fun!"

  13. why "efficient" computation? So, we don't study classes like EXP and NEXP because they are not efficient? or more precisely their problems with efficient solution are already captured by classes like P and NP? Removing the word "efficient" I agree with the definition.

  14. No definition (whether laundry-list or not) will capture all that we do. At the end of the day TCS is "defined" to be what people that call themselves theoretical computer scientists do.

    That said, I can't resist giving another suggestion for a definition:

    The mission of TCS is to understand the principles of computation.

    That is, understand the power and limitations of computing devices (whether man-made or natural) irrespective of current technology.

    The rational for this definition is that what distinguishes TCS is not necessarily the formal and mathematical tools, but the goal of understanding what can and can not be done in principle, rather what can be implemented on machines existing today or 5 years from now.

    While mathematical methods are definitely our main tools, I prefer to give a definition using the goal. Indeed, experimental hueristics with no formal analysis can also be TCS work (if someone came up with such a heuristic that seems to solve SAT on all instances we find that would be a great TCS work).

    Also, I believe that because at the heart of the matter we are more interested in what is true than in what is provable, as a community we are always quick to make assumptions and conjectures (which led to wonderful progress and results).


    p.s. I think it would be nice if people signed their comments.

  15. p.s. -
    just to clarify - doing something in principle does not always mean giving a polynomial-time algorithm to solve a computational problem on a Quantum Turing machine.

    The "something" can be a computational problem, a cryptographic or distributed task, desiging a mechanism. Solving the something "in principle" means to do it in some interesting computational model (e.g., this can be a linear-time RAM machine). And of course, if we come up with the answer that something *can* be done in principle, then we should and do try to see if it can be done today with current technology.


  16. In my opinion the definition of TCS should start with something like:

    "TCS deals with the definition and analysis of mathematical models related to automized forms of computation and communication."

    and then go on to give some examples (turing machines, interactive proofs, etc...).


  17. How about: "TCS deals with the modeling and formal analysis of problems arising in computer science".

    Yes, this is vague (since "computer science" is vague), but that's actually an advantage since now the definition of TCS encompasses more as CS encompasses more...

  18. 1) I have real problems with the ubiquitous attempt at pomo humor in the definition "an 'x' person is someone who is called an 'x' person and they do something called x". No one outside the system gets the humor or is helped in anyway towards understanding.

    2) so what if the laundry list needs updating. math includes logic now but it didn't a hundred (er make that 150) years ago.

    3) Pardon more negativity (and possibly inconsistency), but here goes anyway: I was really taken aback by the inclusion of programming semantics. Yes, it is mathematical, has lots to do with logic (and 'theory B'), lots of theorists do programming semantics relevant research, but as a subject area frankly does not fit well within my conception of 'Theory'. The main desiderata is that a person who they do 'programming semantics' will most likely teach .. hmmm.. programming languages or compilers, hardly ever automata or algorithms. Yes, there's lots of overlap (as with A.I.).

    4) I now realise that whatever definition is chosen, it will almost surely include numerical analysis (or scientific computing) and they may or may not want to be considered on the same team.


  19. How about "the theory of computer science"? Seriously, the title is a pretty good definition, and most definitions suggested here are approaching that ultimate simplicity. If you want a definition of theory, you could say "the mathematics of computer science" instead.

  20. There is a point of view that says that any subject that has "science" in it, isn't really a science. Look for instance at
    "social science" or "political science".
    Not really science, are they. On the other
    hand, the pure sciences do not have "science" in them.

    So computer science isn't really a science.
    Thus, all this effort in defining "the theory of computer science" is futile :-)

  21. So computer science isn't really a science

    That quip was funny twenty years ago. Today anyone who doubts that informatics (aka CS) is a science only displays its ignorance of the field.

  22. I tend to think of theory as an approach or method more than a laundry list. That being said, a lot of the programming languages work (even denotational semantics) does not feel like "canonical theory." This may be a US-specific perspective.

    Aside from a laundry list, you could always try for "theory is what graduate students taking prelims in theory have to study." Depending on where you are, though, that may be wildly different...

    -David Molnar