Department of Theoretical Computer Science

Research Areas Work Groups and Their Seminars Recent Projects Selected Publications Organized Events Department Members

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 relations among complexity classes via standard and non-standard computational models considering both the usual complexity measures like time or space and new ones relevant in neurocomputing and knowledge compilation.

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, Preprocessing Instances for SAT Problem, Knowledge Compilation, Logical Descriptions of Computation, Non-Standard Positional Numeral Systems.

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.

Recent Projects

  • Coalition and Epistemic Logic: An Intensional Approach to Groups (2022-2025; LA GAČR-DFG)
  • Graph limits and beyond (2021-2025; GAČR)
  • AppNeCo: Aproximate Neurocomputing (2022-2024; GAČR)
  • GRADLACT: Graded Logics of Action (2022-2024; GAČR)
  • Metamathematics of substructural modal logics (2022-2024; GAČR)
  • MOSAIC Modalities in Substructural Logics: Theory, Methods and Applications (2021-2024; EU)
  • Random discrete structures (2020-2022, GAČR)
  • Supporting the internationalization of the Institute of Computer Science of the Czech Academy of Sciences (2020-2022, MŠMT ČR)
  • Boolean Representation Languages Complete for Unit Propagation (2019-2021; GAČR)
  • Embedding, Packing and Limits in Graphs (2019-2021; GAČR)
  • FoNeCo: Analytical Foundations of Neurocomputing (2019-2021; GAČR)
  • National Competence Center – Cybernetics and Artificial Intelligence (2019-2021; GAČR)
  • Structural properties of visibility in terrains and farthest color Voronoi diagrams (2019-2021; GAČR)
  • Substructural Modal Logics for Knowledge Representation (2020-2021; AV ČR)
  • CONNECT: Combinatorics of Networks and Computation (2017-2020; H2020 MSCA RISE)
  • Enhancing human resources for research in theoretical computer science (2018-2020; MŠMT)
  • Non-classical Logical Models of Information Dynamics (2018-2020; GAČR)
  • Reasoning with Graded Properties (2018-2020; GAČR)
  • Predicate graded logics and their applications to computer science (2017-2019; GAČR)
  • SYSMICS: Syntax meets semantics: Methods, interactions, and connections in substructural logics (2016-2019; GAČR)
  • Center of Excellence – Institute for Theoretical Computer Science(2012-2018; GAČR)
  • Extremal graph theory and applications (2016-2018; GAČR)
  • Reasoning with Incomplete and Inconsistent Information (AV ČR, 2017)
  • Modelling vague quantifiers in mathematical fuzzy logic (2015-2017; GAČR)
  • An Order-Based Approach to Non-Classical Propositional and Predicate Logics (2013-2016; GAČR)
  • Algebraic Methods in Proof Theory (2011-2015; GAČR)
  • Distribution and metric properties of number sequences and their applications (2012-2015; GAČR)
    •

Selected publications

Organized Events

Department Members

Head: Diana Piguet

Deputy head: Igor Sedlár

Secretarial support: Hana Stříhavková