|
|
|
|
The MFCS conference series on Mathematical Foundations of Computer
Science is a high-quality venue for original research in all branches of
Theoretical Computer Science.
MFCS is among the conferences with the
longest history in the field — the first conference in the series was held
already in 1972. Traditionally, the conference moved between the Czech
Republic, Poland, and Slovakia; while since 2013, the conference has traveled
around Europe.
In 2025, at its round 50th edition, MFCS will be held as a physical event in
Warsaw, Poland.
Poster
Poster is available in following formats:

Important Dates
- Submission Deadline: April 18, 2025 (Anywhere on Earth)
- Rebuttal: June 3–6, 2025
- Author notification: June 20, 2025
- Camera-ready version: July 1, 2025 (AoE)
- Registration opens: July 1, 2025
- Early registration: July 18, 2025 (AoE)
- YRF submission deadline: August 1, 2025
- Conference: August 25–29, 2025 (YRF Workshop on August 24)
Registration
At least one of the authors of each accepted paper must register by July 18 (Early registration phase) for the paper to appear in the proceedings.
Students who at the time of the conference have not yet completed their PhD qualify for the student status of the registration.
Attendee |
Early (until July 18) |
Late (from July 18) |
Regular |
2000 |
2450 |
Student |
1550 |
2000 |
All fees are in Polish złotys. Early registration deadline is July 18, 23:59 (AoE) (the moment of filling in the form counts).
Registration fee includes:
- participation in all conference sessions,
- coffee breaks,
- reception on Aug 25,
- conference dinner on Aug 27.
The conference fee does not include lunches.
Complete your registration online by filling out this form:
MFCS 2025 registration.
Payment
All fees are to be paid by a bank transfer in PLN. Use the following transfer details:
BENEFICIARY:
Uniwersytet Warszawski
ul. Krakowskie Przedmiescie 26/28
00-927 Warszawa
BANK NAME: Bank Millenium SA
IBAN: PL67 1160 2202 0000 0000 6084 9250
SWIFT: BIGBPLPW
Transfer reference template: MFCS2025 <first name> <last name> .
Transfers should reach the organiser's account by August 14, 2025; otherwise the registration may be rejected.
Cancellation policy:
Cancellation requests should be set by e-mail to mfcs2025@mimuw.edu.pl
Cancellations received by July 25 will be eligible for registration fees refund, minus 300 PLN of administrative fee.
Cancellations received after July 25 and no-shows will not be eligible for a refund.
Topics
The program committee encourages submission of original research papers in all areas of theoretical
computer science, including (but not limited to) the following:
- algebraic and co-algebraic methods in computer science
- algorithms and data structures
- automata and formal languages
- bioinformatics
- combinatorics on words, trees, and other structures
- computational complexity (structural and model-related)
- computational geometry
- computer-aided verification
- computer assisted reasoning
- concurrency theory
- cryptography and security
- cyber physical systems, databases and knowledge-based systems
- formal specifications and program development
- foundations of computing
- logics in computer science
- mobile computing
- models of computation
- networks
- parallel and distributed computing
- quantum computing
- semantics and verification of programs
- theoretical issues in artificial intelligence and machine learning
- types in computer science
Invited Speakers
Program Committee
- Shaull Almagor (Technion)
- Nathalie Bertrand (Inria Rennes)
- Udi Boker (Reichman University)
- Gerth Brodal (Aarhus University)
- Michaël Cadilhac (DePaul University)
- Panagiotis Charalampopoulos (Birkbeck, University of London)
- Witold Charatonik (University of Wrocław)
- Dmitry Chistikov (University of Warwick)
- Anuj Dawar (University of Cambridge)
- Joel Day (Loughborough University)
- Moses Ganardi (Max Planck Institute for Software Systems)
- Leszek Gąsieniec (University of Liverpool)
- Paweł Gawrychowski (University of Wrocław) - chair
- Stefan Göller (Universität Kassel)
- Christoph Haase (University of Oxford)
- Meike Hatzel (IBS, Daejeon)
- Jarkko Kari (University of Turku)
- Edon Kelmendi (Queen Mary, University of London)
- Marie Kerjean (CNRS, Université Sorbonne Paris Nord)
- Jakub Kozik (Jagiellonian University)
- László Kozma (Freie Universität Berlin)
- Karoliina Lehtinen (CNRS, LIS Marseille)
- Nutan Limaye (University of Copenhagen)
- Christof Löding (RWTH Aachen)
- Filip Mazowiecki (University of Warsaw) - co-chair
- Pierre Ohlmann (CNRS, LIS Marseille)
- Jakub Opršal (University of Birmingham)
- Guillermo Pérez (University of Antwerp)
- Gabriele Puppis (University of Udine)
- David Purser (University of Liverpool)
- Karin Quaas (Universität Leipzig)
- Chris Schwiegelshohn (Aarhus University)
- Michał Skrzypczak (University of Warsaw) - co-chair
- Tatiana Starikovskaya (ENS Paris)
- Lidia Tendera (University of Opole)
- Karol Węgrzycki (Max Planck Institute for Informatics)
- Philip Wellnitz (National Institute of Informatics)
- Markus Whiteland (Loughborough University)
- Michał Wrona (Jagiellonian University)
- Georg Zetzsche (Max Planck Institute for Software Systems)
- Anna Zych-Pawlewicz (University of Warsaw)
Accepted Papers
- Petr Hlineny.
Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs
- Jingyang Zhao and Mingyu Xiao.
Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
- Günter Rote.
Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton
- Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis and Daniel Vaz.
Parameterized Spanning Tree Congestion
- Jakub Michaliszyn and Jan Otop.
Minimization of Deterministic Finite Automata Modulo the Edit Distance
- Thomas A. Henzinger, Aditya Prakash and K. S. Thejaswini.
Resolving Nondeterminism with Randomness
- Dror Chawin and Ishay Haviv.
New Hardness Results for Low-Rank Matrix Completion
- Bodo Manthey and Jesse van Rhijn.
Counting Locally Optimal Tours in the TSP
- Yael Kirkpatrick and Virginia Vassilevska Williams.
Shortest Paths in Multimode Graphs
- Malory Marin and Rémi Watrigant.
Subcoloring of (Unit) Disk Graphs
- Balder ten Cate, Phokion G. Kolaitis and Arnar Á. Kristjánsson.
Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts
- Jona Dirks and Alexandre Vigny.
Token Sliding Reconfiguration on DAGs
- Noam Shenwald and Orna Kupferman.
Positional-Player Games
- Prosenjit Bose, Pat Morin and Karthik Murali.
Cops and Robbers for Graphs on Surfaces with Crossings
- George Mertzios, Hendrik Molter, Nils Morawietz and Paul Spirakis.
Temporal Graph Realization With Bounded Stretch
- Christoph Berkholz, Moritz Lichter and Harry Vinall-Smeeth.
Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism
- Éléanore Meyer and Jürgen Giesl.
Deciding Termination of Simple Randomized Loops
- Romain Bourneuf, Jana Masaříková, Wojciech Nadara and Marcin Pilipczuk.
Graphs with no long claws: An improved bound for the analog of the Gyárfás’ path argument
- Christoph Grüne and Lasse Wulf.
On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
- Amin Karamlou.
Quantum Relaxations of CSP and Structure Isomorphism
- Benedikt Pago, Anuj Dawar, Erich Grädel and Leon Kullmann.
Symmetric Proofs in the Ideal Proof System
- Vuong Bui and Matthieu Rosenfeld.
A proof of Shur's conjecture on the growth of power-free languages over large alphabets
- Xiaoyang Gong, Bakh Khoussainov and Yuyang Zhuge.
Word structures and their automatic presentations
- Elias Rojas Collins, Chris Köcher and Georg Zetzsche.
The complexity of separability for semilinear sets and Parikh automata
- Florent Ferrari, Emmanuel Hainry, Romain Péchoux and Mario Silva.
Quantum Programming in Polylogarithmic Time
- Léonard Brice, Thomas Henzinger and K. S. Thejaswini.
Finding equilibria: simpler for pessimists, simplest for optimists
- Łukasz Kamiński and Sławomir Lasota.
Reachability in symmetric VASS
- Aliaume Lopez.
Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width
- Benjamin Scheidt and Nicole Schweikardt.
Color Refinement for Relational Structures
- Zeev Nutov.
Tight analysis of the primal-dual method for edge-covering pliable set families
- Zihui Liang, Bakh Khoussainov and Mingyu Xiao.
Deciding regular games: a playground for exponential time algorithms
- Manuel Bodirsky, Edouard Bonnet and Žaneta Semanišinová.
Temporal Valued Constraint Satisfaction Problems
- Manuel Bodirsky and Arno Fehm.
Polynomial-time Tractable Problems over the p-adic Numbers
- Markus Lohrey, Sebastian Maneth and Markus Schmid.
FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree
- Emmanuel Filiot, Nathan Lhote and Pierre-Alain Reynier.
Lexicographic transductions of finite words
- Fabian Egidy, Christian Glaßer and Fynn Godau.
The Complexity of Computing Second Solutions
- Lucie Guillou, Arnaud Sangnier and Nathalie Sznajder.
Wait-Only Broadcast Protocols are Easier to Verify
- Véronique Bruyère, Christophe Grandmont and Jean-François Raskin.
Games with ω-Automatic Preference Relations
- Yudai Egami, Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis and Daniel Vaz.
Broadcasting under Structural Restrictions
- Olivier Bournez, Johanne Cohen and Adrian Wurm.
A Universal Uniform Approximation Theorem for Neural Networks
- Anton Varonka and Kazuki Watanabe.
On Piecewise Affine Reachability with Bellman Operators
- Jan Bok, Jiří Fiala, Nikola Jedličková and Jan Kratochvil.
Computational complexity of covering regular trees
- Gabriele Fici and Estéban Gabory.
Generalized De Bruijn Words, Invertible Necklaces, and the Burrows–Wheeler Transform
- Vittorio Bilò, Andrea D'Ascenzo, Mattia D'Emidio and Giuseppe F. Italiano.
On the Performance of Mildly Greedy Players in k-Coloring Games
- Mrudula Balachander, Emmanuel Filiot, Raffaella Gentillini and Nikos Tzevelekos.
Register Automata with Permutations
- Nicole Schirrmacher, Sebastian Siebertz and Alexandre Vigny.
Elimination Distance to Dominated Clusters
- C.S. Bhargav, Shiteng Chen, Radu Curticapean and Prateek Dwivedi.
Monotone Bounded-Depth Complexity of Homomorphism Polynomials
- Jean Cardinal, Xavier Goaoc and Sarah Wajsbrot.
Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization
- Vojtěch Havlena, Michal Hečko, Lukáš Holík and Ondrej Lengal.
Negated String Containment is Decidable
- Edgar Baucher, François Dross and Cyril Gavoille.
Isometric-Universal Graphs for Trees
- Julia Baligacs, Sofia Brenner, Annette Lutz and Lena Volk.
Symmetry classes of Hamiltonian cycles
- Clotilde Bizière, Thibault Hilaire, Jérôme Leroux and Grégoire Sutre.
On the Reachability Problem for Two-Dimensional Branching VASS
- Alessio Mansutti and Mikhail Starchak.
One-Parametric Presburger Arithmetic has Quantifier Elimination
- Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen and Wiktor Zuba.
Counting Distinct Square Substrings in Sublinear Time
- Morteza Alimi, Tobias Mömke and Michael Ruderer.
Approximating Prize-Collecting Variants of TSP
- Leah Epstein and Asaf Levin.
An EPTAS for minimizing the total weighted completion time of jobs with release dates on uniformly related machines
- Jakub Balabán, Daniel Mock and Peter Rossmanith.
Solving Partial Dominating Set and Related Problems Using Twin-Width
- Stefan Kiefer and Andrew Ryzhikov.
The complexity of reachability problems in strongly connected finite automata
- Antoine Amarilli, Florin Manea, Tina Ringleb and Markus Schmid.
Linear Time Subsequence and Supersequence Regex Matching
- Eike Neumann.
Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space
- Michael Pinsker, Jakub Rydval, Moritz Schöbi and Christoph Spiess.
Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction
- Steven Chaplick, Grzegorz Gutowski and Tomasz Krawczyk.
A Note on the Complexity of Defensive Domination
- Markus Bläser, Radu Curticapean, Julian Dörfler and Christian Ikenmeyer.
Which graph motif parameters count?
- Gabriele Lobbia, Wojciech Różowski, Ralph Sarkis and Fabio Zanasi.
Quantitative Monoidal Algebra: Axiomatising Distance with String Diagrams
- Anand Kumar Narayanan.
Strong keys for tensor isomorphism cryptography
- Yaroslav Alekseev, Yuval Filmus, Ian Mertz, Alexander Smal and Antoine Vinciguerra.
Catalytic Computing and Register Programs Beyond Log-Depth
- Nutan Limaye, Adarsh Srinivasan and Srikanth Srinivasan.
#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank
- Sándor Fekete, Kai Kobbe, Dominik Krupke, Joseph Mitchell, Christian Rieck and Christian Scheffer.
Guarding Offices with Maximum Dispersion
- Jakub Balaban, Matthias Gehnen, Henri Lotze, Finn Seesemann and Moritz Stocker.
Online Knapsack Problems with Estimates
- Antoine Amarilli, Corentin Barloy, Louis Jachiet and Charles Paperman.
Dynamic Membership for Regular Tree Languages
- Valentin Krasotin and Javier Esparza.
Regular model checking for systems with effectively regular reachability relation
- Georg Schindling.
Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification
- Ivan Baburin, Matthew Cook, Florian Grötschla, Andreas Plesner and Roger Wattehofer.
Universality Frontier for Asynchronous Cellular Automata
- John M. Hitchcock, Adewale Sekoni and Hadi Shafei.
Random Permutations in Computational Complexity
- Casper Rysgaard and Sebastian Wild.
Lazy B-Trees
- Andrei Romashchenko.
Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings
- Joris Nieuwveld and Joël Ouaknine.
On Expansions of Monadic Second-Order Logic with Dynamical Predicates
- Florian Luca, Joël Ouaknine and James Worrell.
On Large Zeros of Linear Recurrence Sequences
- Scott Wesley and Julien Ross.
Cutoff Theorems for the Equivalence of Parameterized Quantum Circuits
- Deepu Benson, Balagopal Komarath, Nikhil Mande, Sai Soumya Nalli, Jayalal Sarma and Karteek Sreenivasaiah.
Sensitivity and Query Complexity under Uncertainty
- Rohit Gurjar, Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh and Meirav Zehavi.
Quasipolynomial-Time Deterministic Kernelization and Gammoid Representation
- Go Hashimoto and Daniel Gaina.
Model-theoretic Forcing in Transition Algebra
- Gabriele Fici, Giuseppe Romana, Marinella Sciortino and Cristian Urbina.
Morphisms and BWT-run Sensitivity
- Melissa Antonelli, Arnaud Durand and Juha Kontinen.
Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
- Anupam Das and Abhishek De.
Right-Linear Lattices: An Algebraic Theory of ω-Regular Languages via Fixed Points
- Taisei Nogami and Tachio Terauchi.
Efficient Matching of Some Fundamental Regular Expressions with Backreferences
- Ivan Titov.
Relative randomness and continuous translation functions
- Sriram Bhyravarapu, Pritesh Kumar, Madhumita Kundu, Shivesh K. Roy, Sahiba Sahiba and Saket Saurabh.
Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components
Young Researchers Forum (YRF 2025) — August 24, 2025
Just before MFCS 2025, on August 24, 2025, the Young Researchers Forum (YRF 2025) will take place at the MFCS Conference venue.
This one-day event aims to provide a platform for young researchers, including master’s students, PhD candidates and postdocs, to present and discuss their recent or ongoing work in theoretical computer science in a broad sense, as well as to engage with and learn from more experienced researchers.
All MFCS 2025 participants are warmly invited to attend the sessions of YRF 2025.
The program will consist of:
- session of contributed talks of published, submitted, or in-progress works,
- session of invited non-technical talks addressing various aspects of life and career of young researchers,
- a panel discussion between early-career participants and seasoned researchers, covering various aspects of academic life and research,
- a poster session.
The event will run from 9:30 to 19:00. A detailed schedule will be announced early August.
Registration is free but required as part of the MFCS 2025 registration process.
If you wish to present a talk or a poster, please fill out the submission form before August 1st.
For inquiries about YRF 2025, please contact Bartłomiej Dudek or Lorenzo Clemente.
Conference Venue
The conference will take place at the University of Warsaw Library,
Dobra 56/66, 00-312 Warsaw (location on Google Maps).
The venue is located within walking distance from the following public transport stops:
- Centrum Nauki Kopernik (Metro M2)
- Stare Miasto (trams 4, 13, 20, 23, 26, buses 160, 190)
- Karowa (bus 185)
Conference Dinner
The conference dinner will take place in The Kubicki Arcades, plac Zamkowy 4, 00-307 Warsaw
(location on Google Maps).
It is located within a short walking distance from the public transport stop Stare Miasto
(trams 4, 13, 20, 23, 26; buses 160, 190) and from the conference venue.
The optimal entrance for our participants is from Grodzka street:
here.
Travel Information
Reaching Warsaw by Flight
Warsaw features two airports. The main international hub is Warsaw Chopin Airport (WAW), located south of city centre,
within access by public transport (municipal train S2; buses 146, 175, 188, 331).
Another airport is Warsaw Modlin Airport (WMI), located outside the municipal area, north-west of the city.
It is less conveniently communicated, with connections by taxi, Flixbus (n. 1240), or temporal bus line (denoted ZL).
Reaching Warsaw by Train
Warsaw Central train station is connected by international trains to Berlin, Vienna, Prague, etc.
To reach the conference venue from the central train station use buses (127, 160) or metro M2 line.
Restaurants
The surroundings of the conference venue offer a huge variety of restaurants.
Most of them are rather small places, so it's optimal to organise in groups of 2-6 people.
Multiple vegetarian/vegan options are available.
Among the options is also a modern food-court in Elektrownia Powiśle.
-
Bibenda —
You can book only for groups of size at least 6. Otherwise, around 15 minutes of waiting time. Sharing food vibes, vegetarian friendly.
-
Barbara Nowogrodzka —
A clone of Bibenda (right next to it), similar as above.
-
UKI UKI —
Ramen place. There are many (vegan) Ramen places in Warsaw, try also e.g.V egan Ramen Shop.
-
UKI Green —
Vegan version of above.
-
Peaches —
A bit far (on the other side of the river), but worth checking out. Book at least a week in advance. Vegetarian friendly.
-
Alewino —
A fancy place with good wine. I wouldn't recommend it to vegetarians.
Pubs & Drinks
Local Organisers
For any questions, please don't hesitate to contact us at
mfcs2025@mimuw.edu.pl.
|