Oddělení teoretické informatiky
Členové našeho oddělení se zaměřují na základní aspekty teoretické informatiky a jejich práci lze klasifikovat do tří hlavních oblastí: kombinatorika, matematická logika, výpočetní složitost. Naším cílem v těchto oblastech je nejen dosahovat nových výsledků, ale také rozšiřovat repertoár přístupů, které jsou považovány za standardní. Konkrétně sledujeme tři hlavní cíle:
Kombinatorika: studovat současné zásadní problémy extremální teorie grafů a diskrétních náhodných struktur, a přispět tak k těmto centrálním tématům kombinatoriky, které jsou klíčové například pro naše porozumění velmi velkým sítím.
Matematická logika: vyvinout a aplikovat neklasické logiky pro usuzování v přírozených i umělých scénářích s informacemi z reálného světa, které jsou často nejisté, stupňované nebo dokonce protichůdné a mění se v čase.
Výpočetní složitost: prohloubit naše znalosti vztahů mezi třídami složitosti pomocí standardních i nestandardních výpočetních modelů s přihlédnutím nejen k obvyklým měřítkům složitosti, jako je čas nebo prostor, ale i k novým, která jsou relevantní v neurovýpočtech a kompilaci znalostí.
Oblasti našeho výzkumu
Kombinatorika: Extremální teorie grafů, regularita, pravděpodobnostní metoda, limity grafů, náhodné grafy, diskrétní struktury, výpočetní geometrie, kombinatorické a algebraické metody v teorii čísel.
Matematická logika: Logika a usuzování, stupňované pojmy, vágnost, nejistota, matematická fuzzy logika, substrukturální logiky, parakonzistentní logiky, dynamické a nemonotónní logiky, modální logiky, abstraktní algebraická logika, složitost neklasických logik.
Výpočetní složitost: branching programy, neuronové sítě, booleovské funkce, příprava instancí pro problém SAT, kompilace znalostí, logické popisy výpočtů, nestandardní číselné systémy.
Pracovní skupiny a jejich semináře
Kombinatorická skupina: skupina zaměřená na studium extremální teorie grafů, diskrétních struktur a výpočetní geometrie. Pořádáme kombinatorický seminář ve spolupráci se skupinou Graph limits and inhomogeneous random graphs z Matematického ústavu AV ČR.
LogICS: skupina věnující se studiu (neklasické) logiky. Společně s Českou společností pro kybernetiku a informatiku pořádáme seminář aplikované matematické logiky (nazývaný také Hájkův seminář podle jeho zakladatele), který se pravidelně koná od konce šedesátých let.
Aktuální projekty (zde)
- Limity grafů a související obory (2021-2025; GAČR)
- MOSAIC Modalities in Substructural Logics: Theory, Methods and Applications (2021-2024; EU)
- Náhodné diskrétní struktury (2020-2022, GAČR)
- Podpora internacionalizace ÚI AV ČR, v.v.i. (2020-2022, MŠMT ČR)
- FoNeCo: Analytické základy neurovýpočtů (2019-2021; GAČR)
- Národní centrum kompetence – Kybernetika a umělá inteligence (2019-2021; GAČR)
- Reprezentace booleovských funkcí úplné vzhledem k jednotkové propagaci (2019-2021; GAČR)
- Strukturální vlastnosti viditelnosti terénů a Voroného diagramů nejvzdálenější barvy (2019-2021; GAČR)
- Substrukturální modální logiky pro reprezentaci znalostí (2020-2021; AV ČR)
- Vnořování, pakování a limity v grafech (2019-2021; GAČR)
- CONNECT – Combinatorics of Networks and Computation (2017-2020; H2020 MSCA RISE)
- Neklasické logické modely informační dynamiky (2018-2020; GAČR)
- Rozvoj lidských zdrojů pro výzkum v teoretické informatice (2018-2020; MŠMT)
- Usuzování se škálovanými vlastnostmi (2018-2020; GAČR)
- Predikátové škálované logiky a jejich aplikace v informatice (2017-2019; GAČR)
- SYSMICS: Syntax a sémantika: Metody, interakce a souvislosti v substrukturálních logikách (2016-2019; GAČR)
- Centrum excelence – Institut teoretické informatiky (CE-ITI) (2012-2018; GAČR)
- Extremální teorie grafů a aplikace (2016-2018; GAČR)
- Modelování vágních kvantifikátorů v matematické fuzzy logice (2015-2017; GAČR)
- Neklasické výrokové a predikátové logiky: přístup založený na uspořádání (2013-2016; GAČR)
- Algebraické metody v teorii důkazů (2011-2015; GAČR)
- Distribuční a metrické vlastnosti číselných posloupností a jejich aplikace (2012-2015; GAČR)
Vybrané publikace
- Doležal Martin; Grebík Jan; Hladký Jan; Rocha Israel; Rozhoň Václav. Relating the cut distance and the weak* topology for graphons. Journal of Combinatorial Theory, Series B, 2021
- Kučera P.; Savický Petr. Bounds on the Size of PC and URC Formulas. Journal of Artificial Intelligence Research, 2021
- Badia G.; Cintula Petr; Hájek Petr; Tedder Andrew. How Much Propositional Logic Suffices for Rosser’s Undecidability Theorem? Review of Symbolic Logic, 2020
- Bose P.; Cano P.; Saumell Maria; Silveira R.I. Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs. Computational Geometry-Theory and Applications, 2020
- Bílková Marta; Colacito A. Proof Theory for Positive Logic with Weak Negation. Studia Logica, 2020
- Moraschini Tommaso; Wannenburg J. J. Epimorphism Surjectivity in Varieties of Heyting Algebras. Annals of Pure and Applied Logic, 2020
- Sedlár Igor; Tedder Andrew. Lambek Calculus with Conjugates. Studia Logica, 2020
- Šíma Jiří. Analog Neuron Hierarchy. Neural Networks, 2020
- Allen P.; Böttcher J.; Hladký Jan; Piguet Diana. Packing degenerate graphs. Advances in Mathematics, 2019
- Cintula Petr; Diaconescu D.; Metcalfe G. Skolemization and Herbrand theorems for lattice-valued logics. Theoretical Computer Science, 2019
- Moraschini Tommaso. On the complexity of the Leibniz hierarchy. Annals of Pure and Applied Logic, 2019
- Rozhoň Václav. A Local Approach to the Erdős-Sós Conjecture. SIAM Journal on Discrete Mathematics, 2019
- Šileikis Matas; Warnke L. A counterexample to the DeMarco-Kahn Upper Tail Conjecture. Random Structures and Algorithms, 2019
- 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
- Hladký Jan; Piguet Diana; Simonovits Miklos; Stein Maya; Szemeredi Endre. The approximate Loebl-Komlos-Sos conjecture I, II, III, IV. SIAM Journal on Discrete Mathematics, 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. 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
Organizované akce
