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

Members of the department are mainly active in three interlinked foundational disciplines of theoretical computer science: mathematical logic, computational complexity, discrete mathematics. Our vision is to utilize frontier foundational research to broaden the repertoire of approaches that are considered standard in our respective areas. Our particular aims are:

*Logic: *developing and applying 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 in time.

*Computational complexity:* deepening our knowledge of relations between complexity classes and our understanding of standard and non-standard computational models considering new complexity measures 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.

*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, Computational geometry, Combinatorial and Algebraic Methods in Number Theory, Uniform Distribution of Numerical Sequences, Cryptology.

Combinatorial group: a group dedicated to study of extremal graph theory and computational geometry. Together with group Graph limits and inhomogeneous random graphs from the Institute of Mathematics of the Czech Academy of Sciences we organize a graph theory seminar with emphasis mainly on extremal graph theory

LogICS: a group dedicated to study of (non-classical logics). Together with 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 regularly takes place since the late 1960’s.

- 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)
- 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)

- Kučera Petr;
**Savický Petr**; Vorel Vojtěch. A lower bound on CNF encodings of the at-most-one constraint. Theoretical Computer Science, 2018 **Šíma Jiří; Savický Petr**. Quasi-periodic β – expansions and cut languages. Theoretical Computer Science, 2018- Bezhanishvili Guram;
**Moraschini Tommaso**; Raftery James Gordon. Epimorphisms in Varieties of Residuated Structures. Journal of Algebra, 2017 - Cabello Sergio; Cibulka Josef; Kynčl Jan;
**Saumell Maria**; Valtr Pavel. Peeling Potatoes Near-Optimally in Near-Linear Time. SIAM Journal on Computing, 2017 **Moraschini Tommaso**. A Computational Glimpse at the Leibniz and Frege Hierarchies. Annals of Pure and Applied Logic, 2017**Šíma Jiří; Žák Stanislav**. On tight separation for Blum measures applied to Turing machine buffer complexity. Fundamenta Informaticae, 2017- Böttcher Julia; Hladký Jan;
**Piguet Diana**; Taraz Anusch. An approximate version of the tree packing conjecture. Israel Journal of Mathematics, 2016 **Haniková Zuzana; Savický Petr**. Term satisfiability in FLew-algebras. Theoretical Computer Science 31, 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 - Hladký Jan;
**Piguet Diana**. Loebl-Komlos-Sos Conjecture: dense case. Journal of Combinatorial Theory, 2016 **Chvalovský Karel; Horčík Rostislav**. Full Lambek Calculus with Contraction is Undecidable. Journal of Symbolic Logic, 2016**Moraschini Tommaso**. The Semantic Isomorphism Theorem in Abstract Algebraic Logic. Annals of Pure and Applied 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

- Prague Gathering of Logicians and Beauty of Logic 2018
- 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 Gathering of Logicians 2015
- 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
- Gathering of Prague-Based Logicians 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.
- Kubíková Iveta, Ing.
- Majer Ondrej, RNDr., CSc.
- Moraschini Tommaso
- Piguet Diana, Mgr., Ph.D.
- Porubský Štefan, prof. RNDr., DrSc.
- Punčochář Vít, Ph.D.
- Reggio Luca, Ph.D.
- Rocha De Souza Israel, Dr., Ph.D.
- Saumell Mendiola Maria, Ph.D.
- Savický Petr, RNDr., CSc.
- Sedlár Igor, Mgr., Ph.D.
- Šileikis Matas, Ph.D.
- Šíma Jiří, doc. RNDr., DrSc.
- Tedder Andrew, Ph.D.
- Vidal Wandelmer Amanda, Ph.D.
- Žák Stanislav, RNDr., CSc.