MFCS 2025: 50TH INTERNATIONAL SYMPOSIUM ON MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

A
Alekseev, Yaroslav	Catalytic Computing and Register Programs Beyond Log-Depth
Alimi, Morteza	Approximating Prize-Collecting Variants of TSP
Amarilli, Antoine	Dynamic Membership for Regular Tree Languages Linear Time Subsequence and Supersequence Regex Matching
Antonelli, Melissa	Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
B
Baburin, Ivan	Universality Frontier for Asynchronous Cellular Automata
Balaban, Jakub	Online Knapsack Problems with Estimates Solving Partial Dominating Set and Related Problems Using Twin-Width
Balachander, Mrudula	Register Automata with Permutations
Baligacs, Julia	Symmetry classes of Hamiltonian cycles
Barloy, Corentin	Dynamic Membership for Regular Tree Languages
Baucher, Edgar	Isometric-Universal Graphs for Trees
Benson, Deepu	Sensitivity and Query Complexity under Uncertainty
Berkholz, Christoph	Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism
Bhargav, C.S.	Monotone Bounded-Depth Complexity of Homomorphism Polynomials
Bhyravarapu, Sriram	Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components
Bilò, Vittorio	On the Performance of Mildly Greedy Players in k-Coloring Games
Bizière, Clotilde	On the Reachability Problem for Two-Dimensional Branching VASS
Bläser, Markus	Which graph motif parameters count?
Bodirsky, Manuel	Polynomial-time Tractable Problems over the p-adic Numbers Temporal Valued Constraint Satisfaction Problems
Bok, Jan	Computational complexity of covering regular trees
Bonnet, Edouard	Temporal Valued Constraint Satisfaction Problems
Bose, Prosenjit	Cops and Robbers for Graphs on Surfaces with Crossings
Bourneuf, Romain	Graphs with no long claws: An improved bound for the analog of the Gyárfás’ path argument
Bournez, Olivier	A Universal Uniform Approximation Theorem for Neural Networks
Brenner, Sofia	Symmetry classes of Hamiltonian cycles
Brice, Léonard	Finding equilibria: simpler for pessimists, simplest for optimists
Bruyère, Véronique	Games with ω-Automatic Preference Relations
Bui, Vuong	A proof of Shur's conjecture on the growth of power-free languages over large alphabets
C
Cardinal, Jean	Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization
Chaplick, Steven	A Note on the Complexity of Defensive Domination
Charalampopoulos, Panagiotis	Counting Distinct Square Substrings in Sublinear Time
Chawin, Dror	New Hardness Results for Low-Rank Matrix Completion
Chen, Shiteng	Monotone Bounded-Depth Complexity of Homomorphism Polynomials
Cohen, Johanne	A Universal Uniform Approximation Theorem for Neural Networks
Colcombet, Thomas	Lambdas, Transducers and MSO
Collins, Elias Rojas	The complexity of separability for semilinear sets and Parikh automata
Cook, Matthew	Universality Frontier for Asynchronous Cellular Automata
Curticapean, Radu	Monotone Bounded-Depth Complexity of Homomorphism Polynomials Which graph motif parameters count?
D
D'Ascenzo, Andrea	On the Performance of Mildly Greedy Players in k-Coloring Games
D'Emidio, Mattia	On the Performance of Mildly Greedy Players in k-Coloring Games
Das, Anupam	Right-Linear Lattices: An Algebraic Theory of ω-Regular Languages via Fixed Points
Dawar, Anuj	Symmetric Proofs in the Ideal Proof System
De, Abhishek	Right-Linear Lattices: An Algebraic Theory of ω-Regular Languages via Fixed Points
Dirks, Jona	Token Sliding Reconfiguration on DAGs
Dross, François	Isometric-Universal Graphs for Trees
Durand, Arnaud	Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
Dwivedi, Prateek	Monotone Bounded-Depth Complexity of Homomorphism Polynomials
Dörfler, Julian	Which graph motif parameters count?
E
Egami, Yudai	Broadcasting under Structural Restrictions
Egidy, Fabian	The Complexity of Computing Second Solutions
Epstein, Leah	An EPTAS for minimizing the total weighted completion time of jobs with release dates on uniformly related machines
Esparza, Javier	Regular model checking for systems with effectively regular reachability relation
F
Fehm, Arno	Polynomial-time Tractable Problems over the p-adic Numbers
Fekete, Sándor	Guarding Offices with Maximum Dispersion
Ferrari, Florent	Quantum Programming in Polylogarithmic Time
Fiala, Jiří	Computational complexity of covering regular trees
Fici, Gabriele	Generalized De Bruijn Words, Invertible Necklaces, and the Burrows–Wheeler Transform Morphisms and BWT-run Sensitivity
Filiot, Emmanuel	Register Automata with Permutations Lexicographic transductions of finite words
Filmus, Yuval	Catalytic Computing and Register Programs Beyond Log-Depth
G
Gabory, Estéban	Generalized De Bruijn Words, Invertible Necklaces, and the Burrows–Wheeler Transform
Gaina, Daniel	Model-theoretic Forcing in Transition Algebra
Gavoille, Cyril	Isometric-Universal Graphs for Trees
Gehnen, Matthias	Online Knapsack Problems with Estimates
Gentillini, Raffaella	Register Automata with Permutations
Giesl, Jürgen	Deciding Termination of Simple Randomized Loops
Gima, Tatsuya	Broadcasting under Structural Restrictions
Glaßer, Christian	The Complexity of Computing Second Solutions
Goaoc, Xavier	Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization
Godau, Fynn	The Complexity of Computing Second Solutions
Gong, Xiaoyang	Word structures and their automatic presentations
Grandmont, Christophe	Games with ω-Automatic Preference Relations
Grädel, Erich	Symmetric Proofs in the Ideal Proof System
Grötschla, Florian	Universality Frontier for Asynchronous Cellular Automata
Grüne, Christoph	On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
Guillou, Lucie	Wait-Only Broadcast Protocols are Easier to Verify
Gurjar, Rohit	Quasipolynomial-Time Deterministic Kernelization and Gammoid Representation
Gutowski, Grzegorz	A Note on the Complexity of Defensive Domination
H
Hainry, Emmanuel	Quantum Programming in Polylogarithmic Time
Hanaka, Tesshu	Broadcasting under Structural Restrictions
Hashimoto, Go	Model-theoretic Forcing in Transition Algebra
Haviv, Ishay	New Hardness Results for Low-Rank Matrix Completion
Havlena, Vojtěch	Negated String Containment is Decidable
Henzinger, Thomas	Finding equilibria: simpler for pessimists, simplest for optimists
Henzinger, Thomas A.	Resolving Nondeterminism with Randomness
Hečko, Michal	Negated String Containment is Decidable
Hilaire, Thibault	On the Reachability Problem for Two-Dimensional Branching VASS
Hitchcock, John M.	Random Permutations in Computational Complexity
Hlineny, Petr	Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs
Holík, Lukáš	Negated String Containment is Decidable
I
Ikenmeyer, Christian	Which graph motif parameters count?
Italiano, Giuseppe F.	Higher Connectivity in Directed Graphs On the Performance of Mildly Greedy Players in k-Coloring Games
J
Jachiet, Louis	Dynamic Membership for Regular Tree Languages
Jedličková, Nikola	Computational complexity of covering regular trees
K
Kamiński, Łukasz	Reachability in symmetric VASS
Karamlou, Amin	Quantum Relaxations of CSP and Structure Isomorphism
Khoussainov, Bakh	Deciding regular games: a playground for exponential time algorithms Word structures and their automatic presentations
Kiefer, Stefan	The complexity of reachability problems in strongly connected finite automata
Kirkpatrick, Yael	Shortest Paths in Multimode Graphs
Kobayashi, Yasuaki	Broadcasting under Structural Restrictions
Kobbe, Kai	Guarding Offices with Maximum Dispersion
Kolaitis, Phokion G.	Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts
Komarath, Balagopal	Sensitivity and Query Complexity under Uncertainty
Kontinen, Juha	Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
Krasotin, Valentin	Regular model checking for systems with effectively regular reachability relation
Kratochvil, Jan	Computational complexity of covering regular trees
Krawczyk, Tomasz	A Note on the Complexity of Defensive Domination
Kristjánsson, Arnar Á.	Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts
Krupke, Dominik	Guarding Offices with Maximum Dispersion
Kullmann, Leon	Symmetric Proofs in the Ideal Proof System
Kumar, Pritesh	Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components
Kundu, Madhumita	Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components
Kupferman, Orna	Positional-Player Games
Kyng, Rasmus	Almost-Linear Time Algorithms for Partially Dynamic Graphs
Köcher, Chris	The complexity of separability for semilinear sets and Parikh automata
L
Lampis, Michael	Broadcasting under Structural Restrictions Parameterized Spanning Tree Congestion
Lasota, Sławomir	Reachability in symmetric VASS
Lengal, Ondrej	Negated String Containment is Decidable
Leroux, Jérôme	On the Reachability Problem for Two-Dimensional Branching VASS
Levin, Asaf	An EPTAS for minimizing the total weighted completion time of jobs with release dates on uniformly related machines
Lhote, Nathan	Lexicographic transductions of finite words
Liang, Zihui	Deciding regular games: a playground for exponential time algorithms
Lichter, Moritz	Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism
Limaye, Nutan	#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank
Lobbia, Gabriele	Quantitative Monoidal Algebra: Axiomatising Distance with String Diagrams
Lohrey, Markus	FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree
Lokshtanov, Daniel	Quasipolynomial-Time Deterministic Kernelization and Gammoid Representation
Lopez, Aliaume	Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width
Lotze, Henri	Online Knapsack Problems with Estimates
Luca, Florian	On Large Zeros of Linear Recurrence Sequences
Lutz, Annette	Symmetry classes of Hamiltonian cycles
M
Mande, Nikhil	Sensitivity and Query Complexity under Uncertainty
Manea, Florin	Linear Time Subsequence and Supersequence Regex Matching
Maneth, Sebastian	FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree
Mansutti, Alessio	One-Parametric Presburger Arithmetic has Quantifier Elimination
Manthey, Bodo	Counting Locally Optimal Tours in the TSP
Marin, Malory	Subcoloring of (Unit) Disk Graphs
Masaříková, Jana	Graphs with no long claws: An improved bound for the analog of the Gyárfás’ path argument
Mertz, Ian	Catalytic Computing and Register Programs Beyond Log-Depth
Mertzios, George	Temporal Graph Realization With Bounded Stretch
Meyer, Éléanore	Deciding Termination of Simple Randomized Loops
Michaliszyn, Jakub	Minimization of Deterministic Finite Automata Modulo the Edit Distance
Misra, Pranabendu	Quasipolynomial-Time Deterministic Kernelization and Gammoid Representation
Mitchell, Joseph	Guarding Offices with Maximum Dispersion
Mitsou, Valia	Broadcasting under Structural Restrictions Parameterized Spanning Tree Congestion
Mock, Daniel	Solving Partial Dominating Set and Related Problems Using Twin-Width
Mohamed, Manal	Counting Distinct Square Substrings in Sublinear Time
Molter, Hendrik	Temporal Graph Realization With Bounded Stretch
Morawietz, Nils	Temporal Graph Realization With Bounded Stretch
Morin, Pat	Cops and Robbers for Graphs on Surfaces with Crossings
Murali, Karthik	Cops and Robbers for Graphs on Surfaces with Crossings
Murlak, Filip	On Graph Queries and Modal Constraints
Muscholl, Anca	On Synthesis of Distributed Monitors
Mömke, Tobias	Approximating Prize-Collecting Variants of TSP
N
Nadara, Wojciech	Graphs with no long claws: An improved bound for the analog of the Gyárfás’ path argument
Nalli, Sai Soumya	Sensitivity and Query Complexity under Uncertainty
Narayanan, Anand Kumar	Strong keys for tensor isomorphism cryptography
Nemery, Edouard	Broadcasting under Structural Restrictions Parameterized Spanning Tree Congestion
Neumann, Eike	Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space
Nieuwveld, Joris	On Expansions of Monadic Second-Order Logic with Dynamical Predicates
Nogami, Taisei	Efficient Matching of Some Fundamental Regular Expressions with Backreferences
Nutov, Zeev	Tight analysis of the primal-dual method for edge-covering pliable set families
O
Otachi, Yota	Broadcasting under Structural Restrictions Parameterized Spanning Tree Congestion
Otop, Jan	Minimization of Deterministic Finite Automata Modulo the Edit Distance
Ouaknine, Joël	On Expansions of Monadic Second-Order Logic with Dynamical Predicates On Large Zeros of Linear Recurrence Sequences
P
Pago, Benedikt	Symmetric Proofs in the Ideal Proof System
Panolan, Fahad	Quasipolynomial-Time Deterministic Kernelization and Gammoid Representation
Paperman, Charles	Dynamic Membership for Regular Tree Languages
Pilipczuk, Marcin	Graphs with no long claws: An improved bound for the analog of the Gyárfás’ path argument
Pinsker, Michael	Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction
Plesner, Andreas	Universality Frontier for Asynchronous Cellular Automata
Prakash, Aditya	Resolving Nondeterminism with Randomness
Péchoux, Romain	Quantum Programming in Polylogarithmic Time
R
Radoszewski, Jakub	Counting Distinct Square Substrings in Sublinear Time
Raskin, Jean-François	Games with ω-Automatic Preference Relations
Reynier, Pierre-Alain	Lexicographic transductions of finite words
Rieck, Christian	Guarding Offices with Maximum Dispersion
Ringleb, Tina	Linear Time Subsequence and Supersequence Regex Matching
Romana, Giuseppe	Morphisms and BWT-run Sensitivity
Romashchenko, Andrei	Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings
Rosenfeld, Matthieu	A proof of Shur's conjecture on the growth of power-free languages over large alphabets
Ross, Julien	Cutoff Theorems for the Equivalence of Parameterized Quantum Circuits
Rossmanith, Peter	Solving Partial Dominating Set and Related Problems Using Twin-Width
Rote, Günter	Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton
Roy, Shivesh K.	Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components
Ruderer, Michael	Approximating Prize-Collecting Variants of TSP
Rydval, Jakub	Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction
Rysgaard, Casper	Lazy B-Trees
Rytter, Wojciech	Counting Distinct Square Substrings in Sublinear Time
Ryzhikov, Andrew	The complexity of reachability problems in strongly connected finite automata
Różowski, Wojciech	Quantitative Monoidal Algebra: Axiomatising Distance with String Diagrams
S
Sahiba, Sahiba	Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components
Sangnier, Arnaud	Wait-Only Broadcast Protocols are Easier to Verify
Sarkis, Ralph	Quantitative Monoidal Algebra: Axiomatising Distance with String Diagrams
Sarma, Jayalal	Sensitivity and Query Complexity under Uncertainty
Saurabh, Saket	Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components Quasipolynomial-Time Deterministic Kernelization and Gammoid Representation
Scheffer, Christian	Guarding Offices with Maximum Dispersion
Scheidt, Benjamin	Color Refinement for Relational Structures
Schindling, Georg	Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification
Schirrmacher, Nicole	Elimination Distance to Dominated Clusters
Schmid, Markus	Linear Time Subsequence and Supersequence Regex Matching FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree
Schweikardt, Nicole	Color Refinement for Relational Structures
Schöbi, Moritz	Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction
Sciortino, Marinella	Morphisms and BWT-run Sensitivity
Seesemann, Finn	Online Knapsack Problems with Estimates
Sekoni, Adewale	Random Permutations in Computational Complexity
Semanišinová, Žaneta	Temporal Valued Constraint Satisfaction Problems
Shafei, Hadi	Random Permutations in Computational Complexity
Shenwald, Noam	Positional-Player Games
Siebertz, Sebastian	Elimination Distance to Dominated Clusters
Silva, Mario	Quantum Programming in Polylogarithmic Time
Smal, Alexander	Catalytic Computing and Register Programs Beyond Log-Depth
Spiess, Christoph	Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction
Spirakis, Paul	Temporal Graph Realization With Bounded Stretch
Sreenivasaiah, Karteek	Sensitivity and Query Complexity under Uncertainty
Srinivasan, Adarsh	#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank
Srinivasan, Srikanth	#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank
Starchak, Mikhail	One-Parametric Presburger Arithmetic has Quantifier Elimination
Stocker, Moritz	Online Knapsack Problems with Estimates
Sutre, Grégoire	On the Reachability Problem for Two-Dimensional Branching VASS
Sznajder, Nathalie	Wait-Only Broadcast Protocols are Easier to Verify
T
ten Cate, Balder	Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts
Terauchi, Tachio	Efficient Matching of Some Fundamental Regular Expressions with Backreferences
Thejaswini, K. S.	Resolving Nondeterminism with Randomness Finding equilibria: simpler for pessimists, simplest for optimists
Titov, Ivan	Relative randomness and continuous translation functions
Tzevelekos, Nikos	Register Automata with Permutations
U
Urbina, Cristian	Morphisms and BWT-run Sensitivity
V
van Rhijn, Jesse	Counting Locally Optimal Tours in the TSP
Varonka, Anton	On Piecewise Affine Reachability with Bellman Operators
Vasilakis, Manolis	Broadcasting under Structural Restrictions Parameterized Spanning Tree Congestion
Vassilevska Williams, Virginia	Shortest Paths in Multimode Graphs
Vaz, Daniel	Broadcasting under Structural Restrictions Parameterized Spanning Tree Congestion
Vigny, Alexandre	Token Sliding Reconfiguration on DAGs Elimination Distance to Dominated Clusters
Vinall-Smeeth, Harry	Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism
Vinciguerra, Antoine	Catalytic Computing and Register Programs Beyond Log-Depth
Volk, Lena	Symmetry classes of Hamiltonian cycles
W
Wajsbrot, Sarah	Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization
Walen, Tomasz	Counting Distinct Square Substrings in Sublinear Time
Watanabe, Kazuki	On Piecewise Affine Reachability with Bellman Operators
Watrigant, Rémi	Subcoloring of (Unit) Disk Graphs
Wattehofer, Roger	Universality Frontier for Asynchronous Cellular Automata
Wesley, Scott	Cutoff Theorems for the Equivalence of Parameterized Quantum Circuits
Wild, Sebastian	Lazy B-Trees
Worrell, James	On Large Zeros of Linear Recurrence Sequences
Wulf, Lasse	On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
Wurm, Adrian	A Universal Uniform Approximation Theorem for Neural Networks
X
Xiao, Mingyu	Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity Deciding regular games: a playground for exponential time algorithms
Z
Zanasi, Fabio	Quantitative Monoidal Algebra: Axiomatising Distance with String Diagrams
Zehavi, Meirav	Quasipolynomial-Time Deterministic Kernelization and Gammoid Representation
Zetzsche, Georg	The complexity of separability for semilinear sets and Parikh automata
Zhao, Jingyang	Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
Zhuge, Yuyang	Word structures and their automatic presentations
Zuba, Wiktor	Counting Distinct Square Substrings in Sublinear Time

Disclaimer | Powered by EasyChair Smart Program