Monday, March 9
Tutorial: Regular languages recognition in restricted models of computation, Tatiana Starikovskaya and Gabriel Bathie (chaired by Nguyen Kim Thang)Show/Hide abstract.
Formal language membership is a classical problem with myriad applications. Intuitively, testing membership in a formal language is a classical problem at the core of automata theory and theoretical computer science. At a high level, the goal is to represent a set of strings in a compact way that enables efficient recognition under limited computational resources. A prominent example is regular language recognition, which underlies substring search primitives in modern programming languages.
Motivated by quick growth of data volume and noisy inputs, recent work has revisited regular language recognition in restricted models of computation, where algorithms operate with severe limitations on memory, passes over the input, or access to the data. In this tutorial, we survey recent advances in this direction, focusing in particular on streaming algorithms and property testing for regular language recognition. We will present key techniques, algorithmic results, lower bounds, and structural insights, and conclude with a discussion of open problems and research directions.
- 13:30–14:00: Welcome Coffee
- 14:00–14:40: Tutorial: Regular languages recognition in restricted models of computation (part 1), Tatiana Starikovskaya [slides]
- 14:40–14:45: Break
- 14:45–15:25: Tutorial: Regular languages recognition in restricted models of computation (part 2), Gabriel Bathie [slides]
- 15:25–15:30: Break
- 15:30–16:10: Tutorial: Regular languages recognition in restricted models of computation (part 3), Tatiana Starikovskaya [slides]
- 16:10–16:30: Discussions
Tuesday, March 10
- 09:15–10:10: Welcome Coffee
- 10:10–10:30: Opening, located in Félix Esclangon lecture hall [slides]
-
10:30–12:10:
Parallel sessions
-
[track A] Approximation Algorithms (chaired by Alantha Newman), located in Félix Esclangon lecture hall
- 10:30: A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm, Stefan Hougardy and Bart Zondervan [paper, slides]
- 10:50: A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling, Klaus Jansen and Felix Ohnesorge [paper, slides]
- 11:10: Approximation algorithms for integer programming with resource augmentation, Hauke Brinkop and Hua Chen and Lin Chen and Klaus Jansen and Guochuan Zhang [paper, slides]
- 11:30: Approximating q → p Norms of Non-Negative Matrices in Nearly-Linear Time, Etienne Objois and Adrian Vladu [paper, slides]
- 11:50: Approximate Cartesian Tree Matching with Substitutions, Panagiotis Charalampopoulos and Jonas Ellert and Manal Mohamed [paper, slides]
-
[track B] Complexity and Algorithmic Aspects (chaired by Florin Manea), located in Louis Néel lecture hall
- 10:30: The Complexity of Resilience for Digraph Queries, Manuel Bodirsky and Žaneta Semanišinová [paper, slides]
- 10:50: On the complexity of computing Strahler numbers, Moses Ganardi and Markus Lohrey [paper, slides]
- 11:10: On the Complexity of Language Membership for Probabilistic Words, Antoine Amarilli and Mikaël Monet and Paul Raphaël and Sylvain Salvati [paper, slides]
- 11:30: Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing, Marek Černý and Tim Seppelt [paper, slides]
- 11:50: Efficient Compression in Semigroups, Alexander Thumm and Armin Weiß [paper, slides]
-
[track A] Approximation Algorithms (chaired by Alantha Newman), located in Félix Esclangon lecture hall
- 12:20–14:00: Lunch & Discussions
-
14:00–15:40:
Parallel sessions
-
[track A] Dynamic/Streaming Algorithms (chaired by Moritz Muhlenthaler), located in Félix Esclangon lecture hall
- 14:00: Fully Dynamic Spectral Sparsification for Directed Hypergraphs, Sebastian Forster and Gramoz Goranci and Ali Momeni [paper, slides]
- 14:20: Dynamic Pattern Matching with Wildcards, Arshia Ataee Naeini and Amir-Parsa Mobed and Masoud Seddighin and Saeed Seddighin [paper, slides]
- 14:40: Unit Interval Selection in Random Order Streams, Cezar-Mihail Alexandru and Adithya Diddapur and Magnús M. Halldórsson and Christian Konrad and Kheeran Naidu [paper, slides]
- 15:00: Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics, Justine Cauvi and Nils Morawietz and Laurent Viennot [paper, slides]
- 15:20: Threshold-Driven Streaming Graph: Expansion and Rumor Spreading, Flora Angileri and Andrea Clementi and Emanuele Natale and Michele Salvi and Isabella Ziccardi [paper, slides]
-
[track A] Complexity #1 (chaired by Lisa Hellerstein), located in Louis Néel lecture hall
- 14:00: The Complexity of Homomorphism Reconstruction Revisited, Timo Gervens and Martin Grohe and Louis Härtel and Philipp da Silva Fonseca [paper, slides]
- 14:20: 2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs, Rohit Gurjar and Kilian Rothmund and Thomas Thierauf [paper, slides]
- 14:40: Maker-Maker games of rank 4 are PSPACE-complete, Florian Galliot and Jonas Sénizergues [paper, slides]
- 15:00: Higher Hardness Results for the Reconfiguration of Odd Matchings, Joseph Dorfer [paper, slides]
- 15:20: On the Hardness of the One-Sided Code Sparsifier Problem, Elena Grigorescu and Alice Moayyedi [paper, slides]
-
[track A] Dynamic/Streaming Algorithms (chaired by Moritz Muhlenthaler), located in Félix Esclangon lecture hall
- 15:45–16:15: Coffee Break
-
16:15–17:55:
Parallel sessions
-
[track A] Parameterization & Kernels (chaired by Klaus Jansen), located in Félix Esclangon lecture hall
- 16:15: Structural Parameterization of Steiner Tree Packing, Niko Hastrich and Kirill Simonov [paper, slides]
- 16:35: Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More, Mihail Stoian [paper, slides]
- 16:55: A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs, Thekla Hamm and Sukanya Pandey and Krisztina Szilagyi [paper, slides]
- 17:15: A linear kernel for Independent Set Reconfiguration in Planar Graphs, Nicolas Bousquet and Daniel Cranston [paper, slides]
- 17:35: Kernelization dichotomies for hitting minors under structural parameterizations, Marin Bougeret and Eric Brandwein and Ignasi Sau [paper, slides]
-
[track A] Testing & Counting (chaired by Nguyen Kim Thang), located in Louis Néel lecture hall
- 16:15: Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean functions, Manmatha Roy and Swarnalipa Datta and Manaswi Paraashar and Arijit Ghosh and Chandrima Kayal [paper, slides]
- 16:35: Modular Counting over 3-Element and Conservative Domains, Andrei Bulatov and Amirhossein Kazeminia [paper, slides]
- 16:55: A Permanental analog of Rank-Nullity Theorem for Symmetric Matrices, Surabhi Chakrabartty and Priyanshu Kumar Pant and Ranveer Singh [paper, slides]
- 17:15: Testing H-freeness on sparse graphs, the case of bounded expansion, Samuel Humeau and Mamadou Kanté and Daniel Mock and Timothé Picavet and Alexandre Vigny [paper, slides]
- 17:35: Counting Unit Circular Arc Intersections, Haitao Wang [paper, slides]
-
[track A] Parameterization & Kernels (chaired by Klaus Jansen), located in Félix Esclangon lecture hall
- 18:10–20:10: Reception
Wednesday, March 11
- 09:00–10:00: Invited Talk: Advancements in Online Edge Coloring Algorithms, Ola Svensson [paper, slides] (chaired by Nguyen Kim Thang)
- 10:00–10:30: Coffee Break
-
10:30–12:10:
Parallel sessions
-
[track A] Random Structures (chaired by Bruno Gaujal), located in Félix Esclangon lecture hall
- 10:30: Planting and MCMC Sampling from the Potts model, Andreas Galanis and Leslie Ann Goldberg and Paulina Smolarova [paper, slides]
- 10:50: The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs, Zylan Benjert and Kostas Lakis and Johannes Lengler and Raghu Raman Ravi [paper, slides]
- 11:10: Broadcast in Almost Mixing Time, Anton Paramonov and Roger Wattenhofer [paper, slides]
- 11:30: Modularity of preferential attachment graphs, Katarzyna Rybarczyk and Małgorzata Sulkowska [paper, slides]
- 11:50: Computational hardness of estimating quantum entropies via binary entropy bounds, Yupan Liu [paper, slides]
-
[track B] Computability & Logic (chaired by David Monniaux), located in Louis Néel lecture hall
- 10:30: Decidability of Extensions of Presburger Arithmetic by Hardy Field Functions, Hera Brown and Jakub Konieczny [paper, slides]
- 10:50: Effective Versions of Strong Measure Zero, Matt Rayman [paper, slides]
- 11:10: Generalised Quantifiers Based on Rabin-Mostowski Index, Denis Kuperberg and Damian Niwinski and Paweł Parys and Michał Skrzypczak [paper, slides]
- 11:30: On the p-adic Skolem Problem, Piotr Bacik and Joël Ouaknine and David Purser and James Worrell [paper, slides]
- 11:50: The asymptotic size of finite irreducible semigroups of rational matrices, Stefan Kiefer and Andrew Ryzhikov [paper, slides]
-
[track A] Random Structures (chaired by Bruno Gaujal), located in Félix Esclangon lecture hall
- 12:20–14:00: Lunch & Discussions
-
14:00–15:40:
Parallel sessions
-
[track A] Algorithm Analysis (chaired by Guochuan Zhang), located in Félix Esclangon lecture hall
- 14:00: Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach, Antoine Joux and Karol Węgrzycki [paper, slides]
- 14:20: Lower bounds for ranking-based pivot rules, Yann Disser and Georg Loho and Matthew Maat and Nils Mosis [paper, slides]
- 14:40: When is local search both effective and efficient?, Artem Kaznatcheev and Sofia Vazquez Alferez [paper, slides]
- 15:00: Refining the Complexity Landscape of Speed Scaling: Hardness and Algorithms, Antonios Antoniadis and Denise Graafsma and Ruben Hoeksma and Maria Vlasiou [paper, slides]
- 15:20: Optimal Average Disk-Inspection via Fermat's Principle, Konstantinos Georgiou [paper, slides]
-
[track B] Games & Automata (chaired by Sylvain Schmitz), located in Louis Néel lecture hall
- 14:00: One-clock synthesis problems, Sławomir Lasota and Mathieu Lehaut and Julie Parreaux and Radosław Piórkowski [paper, slides]
- 14:20: A pumping-like lemma for languages over infinite alphabets, Yoav Danieli [paper, slides]
- 14:40: Algorithm and Strategy Construction for Sure-Almost-Sure Stochastic Parity Games, Laurent Doyen and Shibashis Guha [paper, slides]
- 15:00: Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata, Filip Mazowiecki and Antoni Puch and Daniel Smertnig [paper, slides]
- 15:20: Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata, Bruno Guillon and Luca Prigioniero and Javad Taheri [paper, slides]
-
[track A] Algorithm Analysis (chaired by Guochuan Zhang), located in Félix Esclangon lecture hall
- 15:45–16:15: Coffee Break
-
16:15–17:55:
Parallel sessions
-
[track A] Graph parameters (chaired by Nicolas Bousquet), located in Félix Esclangon lecture hall
- 16:15: A polynomial bound on the pathwidth of graphs edge-coverable by k shortest paths, Julien Baste and Lucas De Meyer and Ugo Giocanti and Etienne Objois and Timothé Picavet [paper, slides]
- 16:35: Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors, Roohani Sharma and Michał Włodarczyk [paper, slides]
- 16:55: Computing Twin-Width via Treedepth and Vertex Integrity, Robert Ganian and Mathis Rocton [paper, slides]
- 17:15: Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density, Tom-Lukas Breitkopf and André Nichterlein and Vincent Froese and Anton Herrmann and Matthias Bentert [paper, slides]
- 17:35: Colouring Probe H-Free Graphs, Daniel Paulusma and Johannes Rauch and Erik Jan van Leeuwen [paper, slides]
-
[track A] Complexity #2 (chaired by Alexei Bulatov), located in Louis Néel lecture hall
- 16:15: Smaller Circuits for Bit Addition, Mikhail Goncharov and Alexander Kulikov and Georgii Levtsov [paper, slides]
- 16:35: Simple Circuit Extensions for XOR in PTIME, Marco Carmosino and Ngu Dang and Tim Jackman [paper, slides]
- 16:55: Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank, Nikolai Chukhin and Alexander Kulikov and Ivan Mihajlin and Arina Smirnova [paper, slides]
- 17:15: A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity, Pavel Dvořák and Bruno Loff and Suhail Sherif [paper, slides]
- 17:35: Upper and Lower Bounds for the Linear Ordering Principle, Edward Hirsch and Ilya Volkovich [paper, slides]
-
[track A] Graph parameters (chaired by Nicolas Bousquet), located in Félix Esclangon lecture hall
- 18:00–19:00: Business Meeting [stacs2026], [stacs2027], [theoretics]
Thursday, March 12
- 09:00–10:00: Invited Talk: Moments in Time: Algebraic Analysis for Solvable Loops, Laura Kovács [paper, slides] (chaired by Florin Manea)
- 10:00–10:30: Coffee Break
-
10:30–11:50:
Parallel sessions
-
[track A] Online/Dynamic Algorithms (chaired by Bertrand Simon), located in Félix Esclangon lecture hall
- 10:30: To Buy or Not to Buy: Online Rent-or-Buy on Node-Weighted Graphs, Sander Borst and Moritz Venzin [paper, slides]
- 10:50: Stealing From the Dragon's Hoard: Online Unbounded Knapsack With Removal, Matthias Gehnen and Moritz Stocker [paper, slides]
- 11:10: Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid, Haya Diwan and Lisa Hellerstein and Nicole Megow and Jens Schlöter [paper, slides]
- 11:30: A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP, Andreas Kalavas and Charalampos Platanos and Thanos Tolias [paper, slides]
-
[track A] Games & Strings (chaired by Nguyen Kim Thang), located in Louis Néel lecture hall
- 10:30: Computing Tarski Fixed Points in Financial Networks, Leander Besting and Martin Hoefer and Lars Huth [paper, slides]
- 10:50: The communication complexity of combinatorial auctions in graphs, George Christodoulou and Elias Koutsoupias and Annamaria Kovacs and Ioannis Vlachos [paper, slides]
- 11:10: Time-Optimal Construction of String Synchronizing Sets, Jonas Ellert and Tomasz Kociumaka [paper, slides]
- 11:30: Relative Compressed Reverse Suffix Array, Sharma Thankachan and Rahul Shah and M. Oguzhan Kulekci and Mano Prakash Parthasarathi [paper, slides]
-
[track A] Online/Dynamic Algorithms (chaired by Bertrand Simon), located in Félix Esclangon lecture hall
- 11:55–12:10: Group photo
- 12:10–13:00: Lunch, located at IMAG building
- 13:10: Bus departure for snowshoe outing
- 17:30–18:00: (estimated) Return to Grenoble
- 19:30: Conference Dinner at Per’Gras restaurant, reachable by foot or by cable car
Friday, March 13
- 09:00–10:00: Invited Talk: Query Languages for Machine-Learning Models, Martin Grohe [paper, slides] (chaired by Nguyen Kim Thang)
- 10:00–10:30: Coffee Break
-
10:30–12:10:
Parallel sessions
-
[track A] Graphs & Algorithms (chaired by Louis Esperet), located in Félix Esclangon lecture hall
- 10:30: Circle graphs can be recognized in linear time, Christophe Paul and Ignaz Rutter [paper, slides]
- 10:50: List coloring ordered graphs with forbidden induced subgraphs, Marta Piecyk and Paweł Rzążewski [paper, slides]
- 11:10: Optimal Deterministic Rendezvous in Labeled Lines, Yann Bourreau and Ananth Narayanan and Alexandre Nolin [paper, slides]
- 11:30: Line Cover and Related Problems, Matthias Bentert and Fedor V. Fomin and Petr Golovach and Souvik Saha and Sanjay Seetharaman and Anannya Upasana [paper, slides]
- 11:50: Maximum Reachability Orientation of Mixed Graphs, Florian Hörsch [paper, slides]
-
[track B] Logic & Language Theory (chaired by Olaf Beyersdorff), located in Louis Néel lecture hall
- 10:30: Demystifying Codensity Monads via Duality, Fabian Lenke and Stefan Milius and Henning Urbat and Nico Wittrock [paper, slides]
- 10:50: Guarded Logic and Random Models, Oskar Fiuk [paper, slides]
- 11:10: An Improved Version of Hmelevskii's Theorem on Three-Variable Word Equations, Aleksi Saarela [paper, slides]
- 11:30: Algebraic characterizations of classes of regular languages in DynFO, Corentin Barloy and Felix Tschirbs and Nils Vortmeier and Thomas Zeume [paper, slides]
- 11:50: On Effective Banach-Mazur Games and an application to the Poincaré Recurrence Theorem for Category, Prajval Koul and Satyadev Nandakumar [paper, slides]
-
[track A] Graphs & Algorithms (chaired by Louis Esperet), located in Félix Esclangon lecture hall
- 12:20–14:00: Lunch & Discussions