Two research papers authored by members of the GGOAT Research Group and the Algorithms Laboratory at the Faculty of Information Technology, Czech Technical University in Prague (FIT CTU), have been accepted to the main track of the 53rd International Colloquium on Automata, Languages and Programming (ICALP). This achievement is particularly notable as ICALP was newly ranked in the highest A* category this year. Both papers were selected from an exceptionally competitive field of 628 submissions, with only 190 papers accepted to the scientific program following a rigorous peer-review process.
The first paper, "Inapproximability of Counting Permutation Patterns," investigates the computational limits and inapproximability of the problem of counting permutation patterns. The results contribute to a deeper understanding of algorithmic complexity in combinatorics and theoretical computer science. An additional distinction is that the paper is a single-author publication. Its sole author, Michal Opler, Ph.D., of FIT CTU, presented his research findings in person during a conference talk.
"I was thrilled to present my work at ICALP in such a highly competitive environment. Discussing my results with leading experts from around the world provided me with valuable insights and inspiration for my future research," says Michal Opler.
The second paper, "Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees," examines the precise computational limits and lower bounds for finding spanning trees with explicitly bounded maximum vertex degree. The research aims to provide a deeper understanding of the structural properties that determine the time complexity and theoretical limits of graph algorithms. The paper is co-authored by Narek Bojikian (Humboldt University of Berlin), Alexander Firbas (TU Wien), Robert Ganian (TU Wien), Hung P. Hoang (TU Wien), and Krisztina Szilágyi, Ph.D. (FIT CTU).
ICALP is the flagship conference of the European Association for Theoretical Computer Science (EATCS). Its mission is to promote fundamental research and facilitate scientific exchange among researchers, academics, and students working in algorithms, computational complexity, automata theory, and related areas of mathematics and theoretical computer science. This year's conference took place from 6 to 10 July 2026 at Royal Holloway, University of London, United Kingdom.
