Hned dva články prezentující výsledky výzkumníků z výzkumné skupiny GGOAT a Laboratoře algoritmů Fakulty informačních technologií ČVUT v Praze (FIT ČVUT) byly přijaty do hlavního programu 53. ročníku mezinárodní konference ICALP (International Colloquium on Automata, Languages and Programming). Významným úspěchem je také skutečnost, že konference byla letos nově zařazena do nejvyšší kategorie hodnocení A*. Obě publikace obstály v mimořádně silné konkurenci 628 zaslaných vědeckých prací, z nichž bylo na základě náročného recenzního řízení do vědeckého programu vybráno pouze 190.
První článek s názvem „Inapproximability of Counting Permutation Patterns“ se zabývá výpočetními limity a mezemi aproximovatelnosti problému počítání permutačních vzorů. Výsledky přispívají k hlubšímu porozumění algoritmické složitosti v kombinatorice a teoretické informatice. Významným úspěchem je také skutečnost, že jde o samostatnou autorskou práci (tzv. single-author paper). Jejím jediným autorem je Mgr. Michal Opler, Ph.D. z FIT ČVUT, který výsledky svého výzkumu na konferenci osobně představil formou přednášky.
„Byl jsem nadšen, že jsem mohl svou práci prezentovat na konferenci ICALP v tak silné konkurenci. Mohl jsem diskutovat své výsledky s předními světovými experty a přineslo mi to mnoho podnětů pro budoucí výzkum,“ říká Michal Opler.
Druhý článek s názvem „Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees“ zkoumá přesné výpočetní limity a dolní meze pro hledání koster grafů s explicitně omezeným maximálním stupněm vrcholů. Cílem výzkumu je hlubší pochopení strukturálních souvislostí, které ovlivňují časovou náročnost a teoretické limity grafových algoritmů. Autory článku jsou Narek Bojikian (Humboldt Universität zu Berlin), Alexander Firbas (TU Wien), Robert Ganian (TU Wien), Hung P. Hoang (TU Wien) a Krisztina Szilágyi, Ph.D. (FIT ČVUT).
Konference ICALP je stěžejní akcí Evropské asociace pro teoretickou informatiku (EATCS). Jejím cílem je podporovat fundamentální výzkum a usnadňovat vědeckou výměnu mezi výzkumníky, vědci a studenty v oblasti algoritmů, výpočetní složitosti, automatů a souvisejících matematických disciplín. Letošní ročník se konal od 6. do 10. července 2026 na britské Royal Holloway, University of London.
