Department of Theoretical Computer Science

Members of our department are mainly active in three interlinked foundational disciplines of theoretical computer science: mathematical logic, computational complexity, discrete mathematics.

Theoretical computer science, or TCS, makes use of mathematical methods to describe, understand and analyze various aspects of computing and computer science in general.

Current trends

The ever growing computational power of computers increases the size of problems computer science can and wants to address and presents new challenges. New effective methods for processing, structuring, describing, and reasoning with real-life information/data are developed and TCS aims not only at being part of this development but also at providing a deeper understanding of underlying foundational phenomena.

Our vision

Logic: developing and applying non-classical logics for reasoning, in both natural and artificial scenarios, with real-life information, which is often uncertain, graded, or even contradictory and changing in time.

Computational complexity: deepening our knowledge of relations between complexity classes and investigating standard and non-standard computational models considering both the usual complexity measures like time and space and new ones related to current technological challenges.

Discrete mathematics: exploring extremal graph theory and applied number theory and using the achieved results in cryptography, theory of computing, and the study of randomness.

Substantiation of the vision

To pursue our vision we do frontier foundational research with the aim to broaden the repertoire of approaches that are considered standard in our respective areas. Our present research focus can be best described by the following keywords:

Logic: Mathematical Fuzzy Logic, Substructural Logics, Vagueness, Paraconsistent Logic, Logic and Reasoning, Graded notions, Dynamic and Non-Monotonic Logic, Modal Logic, Abstract Algebraic Logic, Complexity of Non-Classical Logics

Computational complexity: Branching Programs, Neural Networks, Boolean Functions, SAT Problem Preprocessing, Logical Descriptions of Computation, Non-Standard Positional Numeral Systems

Discrete mathematics: Extremal Graph Theory, Regularity Method, Probabilistic Method, Limits of Graphs, Random Graphs, Combinatorial and Algebraic Methods in Number Theory, Uniform Distribution of Numerical Sequences, Cryptology


  • Our department organizes jointly with the Czech Society for Cybernetics and Informatics a seminar on applied mathematical logic (also called Hájek’s seminar according to its founder) which regularly takes place since the late 1960’s. The program can be found here.
  • We are organising a graph theory seminar with emphasis on extremal graph theory. The program can be found here.

Running projects (here)

  • Enhancing human resources for research in theoretical computer science
  • Center of Excellence – Institute for Theoretical Computer Science
  • Extremal graph theory and applications
  • Predicate graded logics and their applications to computer science
  • Non-classical Logical Models of Information Dynamics
  • Reasoning with Graded Properties

 Selected publications

Department members

Secretarial support