Theoretical computer science

From Example Problems
Jump to: navigation, search

Theoretical computer science is the collection of topics of computer science that focuses on the more abstract and mathematical aspects of computing, such as the theory of computation, analysis of algorithms and semantics of programming languages. Although not itself a single topic, its practitioners form a distinct subgroup within computer science researchers.


It is not easy to circumscribe the theory areas precisely; the ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT), which describes its mission as the promotion of theoretical computer science, says

"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."

Even so, the "theory people" in CS self-identify as different. Some characterize themselves as doing the "'science' underlying the field of computing"[1], although this neglects the experimental science done in non-theoretical areas such as software system research.


  • EATCS, the european association for Theoretical Computer Science
  • Dutch Association for Theoretical Computer Science [2]

Journals and newsletters


  • Algebraic Methodology And Software Technology (AMAST)
  • IEEE Symposium on Logic in Computer Science (LICS)
  • Annual ACM Symposium on the Theory of Computing (STOC)


External links