Oddělení teoretické informatiky

	Oblasti výzkumu	Pracovní skupiny a jejich semináře	Aktuální projekty	Vybrané publikace	Organizované akce	Členové oddělení

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 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 (více info)

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)
Reasoning with Incomplete and Inconsistent Information (AV ČR, 2017)
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; Komlós J; Piguet Diana; Simonovits Miklos; Stein Maya; Szemeredi Endre. The approximate Loebl-Komlós-Sós 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-Komlós-Sós 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