Institute of Computer Science

The Czech Academy of Sciences

The Czech Academy of Sciences

"Simplicity is a great virtue but it requires hard work to achieve it and education to appreciate it. And to make matters worse: complexity sells better." - E. W. Dijkstra

The 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** makes use of mathematical methods to describe, understand and analyze various aspects of computing and computer science in general.

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

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

*Computational complexity:* deepening our knowledge of relations among complexity classes and investigating the 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.

To pursue our vision we perform 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.

- Modelling vague quantifiers in mathematical fuzzy logic
- Center of Excellence – Institute for Theoretical Computer Science
- An Order-Based Approach to Non-Classical Propositional and Predicate Logics
- Totally ordered monoids
- Extremal graph theory and applications
- Predicate graded logics and their applications to computer science

- Kučera, Petr; Savický, Petr; Vorel, Vojtěch. A Lower Bound on CNF Encodings of the At-Most-One Constraint. Proc. of SAT 2017. (extended version)
- Böttcher, Julia; Hladký, Jan; Piguet Diana; Taraz Anusch. An approximate version of the tree packing conjecture. Israel Journal of Mathematics, 2016
- Hladký, Jan; Piguet, Diana; Simonovits, Miklos; Stein, Maya; Szemeredi, Endre. The approximate Loebl-Komlos-Sos conjecture and embedding trees in sparse graphs. Electronic Research Announcements in Mathematical Sciences, 2016
- Chvalovský, Karel; Horčík, Rostislav. Full Lambek Calculus with Contraction is Undecidable. Journal of Symbolic Logic, 2016
- Strauch Oto; Porubský Štefan. Distribution of Sequences: A Sampler. Peter Lang GmbH, Electronic revised version December 8, 2016.
- Cintula, Petr (ed.); Fermüller, C. (ed.); Hájek, Petr (ed.), Noguera, Carles (ed.). Handbook of Mathematical Fuzzy Logic (in three volumes). London: College Publications, 2011, 2015.
- Cintula, Petr; Noguera, Carles. A Henkin-Style Proof of Completeness for First-Order Algebraizable Logics. Journal of Symbolic Logic, 2015
- Chvalovský, Karel. Undecidability of consequence relation in Full Non-associative Lambek Calculus. Journal of Symbolic Logic, 2015
- Horčík, Rostislav. Word Problem for Knotted Residuated Lattices. Journal of Pure and applied Algebra, 2015
- Marco, František; Porubský Štefan. Topological Aspects of Onfinitude of Primes in Aritmetic Pregressions, Colloquium Mathematicum, 2015
- Šíma, Jiří. Energy Complexity of Recurrent Neural Networks. Neural Computation 2014
- Šíma, Jiří; Žák, Stanislav. Almost k-wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs. Proc. of CSR 2011. (extended version)

- 23rd Czech and Slovak International Conference on Number Theory 2017
- Topology, Algebra, and Categories in Logic 2017
- Non-classical Modal and Predicate Logics 2017
- Prague seminar: The Future of Mathematical Fuzzy Logic 2016
- Prague seminar on Non-Classical Mathematics 2015
- 4th International Conference on Uniform Distribution Theory 2014
- Prague Seminar on Substructural Logics 2014
- 2nd Prague Symposium on Semilinear Logics 2013
- 21st Czech and Slovak International Conference on Number Theory 2013
- Manyval 2013
- ALANT Joint Conferences on Algebra, Logic and Number Theory 2012
- 20th Czech and Slovak International Conference on Number Theory 2011
- Logic, Algebra and Truth Degrees 2010
- 19th Czech and Slovak International Conference on Number Theory 2009
- 9th Central European Conference on Cryptography 2009
- 5th Polish, Slovak and Czech Conference on Number Theory 2004

- Bílková Marta, Mgr., Ph.D.
- Cintula Petr, doc.Ing., Ph.D.
- Haniková Zuzana, RNDr., Ph.D.
- Harmancová Dagmar, prom.mat.
- Horčík Rostislav, Ing., Ph.D.
- Kubíková Iveta, Ing.
- Majer Ondrej, RNDr., CSc.
- Moraschini Tommaso
- Pelekis Christos, Ph.D.
- Petrík Milan, Ing., Ph.D.
- Piguet Diana, Mgr., Ph.D.
- Porubský Štefan, prof. RNDr., DrSc.
- Přenosil Adam, Mgr.
- Rocha De Souza Israel, Dr., Ph.D.
- Rozhoň Václav
- Saumell Mendiola Maria, Ph.D.
- Savický Petr, RNDr., CSc.
- Sedlár Igor, Mgr., Ph.D.
- Šíma Jiří, doc. RNDr., DrSc.
- Vidal Wandelmer Amanda, Ph.D.
- Žák Stanislav, RNDr., CSc.