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.
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.
MathematicalLogic: 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.
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.
Hladký Jan; Komlós J; Piguet Diana;
Simonovits Miklos; Stein Maya; Szemerédi Endre. The approximate
Loebl-Komlós-Sós conjecture I, II, III, IV. SIAM Journal on Discrete Mathematics, 2017
