Department of Theoretical Computer Science

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 understating of very large networks.

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.

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.

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

Computational Complexity: Branching Programs, Neural Networks, Boolean Functions, Preprocessing Instances for SAT Problem, Knowledge Compilation, Logical Descriptions of Computation, Non-Standard Positional Numeral Systems.

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.

Work groups and their seminars

Combinatorial group: a group dedicated to study of extremal graph theory, discrete structures, and computational geometry. In collaboration with the group Graph limits and inhomogeneous random graphs from the Institute of Mathematics of the Czech Academy of Sciences we organize a combinatorial seminar .

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

Recent projects (here)

  • FoNeCo: Analytical Foundations of Neurocomputing (2019-2021; GAČR)
  • National Competence Center – Cybernetics and Artificial Intelligence (2019-2021; GAČR)
  • Boolean Representation Languages Complete for Unit Propagation (2019-2021; GAČR)
  • Structural properties of visibility in terrains and farthest color Voronoi diagrams (2019-2021; GAČR)
  • Embedding, Packing and Limits in Graphs (2019-2021; GAČR)
  • 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)
  • CONNECT – Combinatorics of Networks and Computation (2017-2020; H2020 MSCA RISE)
  • 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)
  • Extremal graph theory and applications (2016-2018; GAČR)
  • 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)
  • Center of Excellence – Institute for Theoretical Computer Science (2012-2018; GAČR)
  • Distribution and metric properties of number sequences and their applications (2012-2015; GAČR)
  • Algebraic Methods in Proof Theory (2011-2015; GAČR)

 Selected publications

Organized events

 

Department Members

Head: Petr Cintula

Secretarial support: Iveta Kubíková