Department of Theoretical Computer Science

Members of our department are focused on the more foundational aspects of Theoretical Computer Science and their work can be classified into three main areas: Combinatorics, Computational Complexity, and Mathematical Logic. In all these areas, we strive not only to achieve new results but to broaden the repertoire of approaches that are considered standard. In particular we pursue three main aims:

Combinatorics: to study the recent challenging problems of extremal graph theory and discrete random structures, and thus contribute to these central topics in combinatorics which are crucial e.g. for our understanding of very large networks.

Mathematical Logic: to develop and apply 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 over time.

Computational Complexity: to deepen our knowledge of both standard and non-standard computational models, taking into account not only the usual complexity measures such as time and space, but also new ones that are relevant to the complexity of algorithms for specific tasks in neurocomputing, knowledge compilation, and combinatorial optimization.

Research Areas

Combinatorics: Extremal Graph Theory, Regularity Method, Probabilistic Method, Limits of Graphs, Random Graphs, Discrete Structures, Computational Geometry, Combinatorial and Algebraic Methods in Number Theory.

Mathematical Logic: Logic and Reasoning, Graded Notions, Vagueness, Uncertainty, Mathematical Fuzzy Logic, Substructural Logics, Paraconsistent Logic, Dynamic and Non-Monotonic Logic, Modal Logic, Abstract Algebraic Logic, Complexity of Non-Classical Logics, Philosophy of Mathematics.

Computational Complexity: Branching Programs, Neural Networks, Boolean Functions, Propagation Strength in Instances for SAT Problem, Knowledge Compilation, Logical Descriptions of Computation, Energy Complexity.

Work Groups and Their Seminars

Combinatorial group: a group dedicated to study of extremal graph theory, discrete structures, graph limits, and computational geometry. We organize a combinatorial seminar.

LogICS: the group focuses on the study of (non-classical) logic. With the Czech Society for Cybernetics and Informatics, we organize a seminar of applied mathematical logic (also called Hájek’s seminar according to its founder), which has run continuously since the late 1960’s.

Implemented Projects

Selected publications

Organized Events

Department Members

Core researchers

Project staff

Head: Diana Piguet

Deputy head: Igor Sedlár

Secretarial support: Hana Stříhavková