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, Slovakia, and Poland, while since 2013, the conference has traveled around Europe.

In 2024, at its 49th edition, MFCS will be held as a physical event in Bratislava, Slovakia.

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

On-site registration

• Sunday August 25th, 18:00-21:00
• Monday August 26th, from 8:00

Schedule

Invited talks

Monday, August 26, 9:00-10:00

Tuesday, August 27, 9:00-10:00

Wednesday, August 28, 9:00-10:00

Thursday, August 29, 9:00-10:00

Friday, August 30, 9:00-10:00

Session 1

Monday, August 26, 10:30-12:00

Session 1A

Session 1B

Session 2

Monday, August 26, 14:00-15:30

Session 2A

Session 2B

Session 3

Monday, August 26, 16:00-17:30

Session 3A

Session 3B

Session 4

Tuesday, August 27, 10:30-12:00

Session 4A

Session 4B

Session 5

Tuesday, August 27, 14:00-15:30

Session 5A

Session 5B

Session 6

Tuesday, August 27, 16:00-17:30

Session 6A

Session 6B

Session 7

Wednesday, August 28, 10:30-12:00

Session 7A

Session 7B

Session 8

Wednesday, August 28, 14:00-15:30

Session 8A

Session 8B

Session 9

Wednesday, August 28, 16:00-17:30

Session 9A

Session 9B

Session 10

Thursday, August 29, 10:30-12:00

Session 10A

Session 10B

Session 11

Thursday, August 29, 14:00-15:30

Session 11A

Session 11B

Session 12

Thursday, August 29, 16:00-17:30

Session 12A

Session 12B

Session 13

Friday, August 30, 10:30-12:00

Session 13A

Session 13B

Session 14

Friday, August 30, 14:00-15:00

Session 14A

Session 14B

Program Committee

• Christel Baier (TU Dresden)
• Petra Berenbrink (Universität Hamburg)
• Christoph Berkholz (TU Ilmenau)
• Michael Blondin (Université de Sherbrooke)
• Mikolaj Bojanczyk (University of Warsaw)
• Joan Boyar (University of Southern Denmark)
• Brona Brejova (Comenius University in Bratislava)
• Jean Cardinal (Université libre de Bruxelles)
• Pavol Cerny (TU Wien)
• Krishnendu Chatterjee (Institute of Science and Technology, Austria)
• Ugo Dal Lago (University of Bologna)
• Stefan Dobrev (Slovak Academy of Sciences)
• Robert Elsässer (University of Salzburg)
• Leah Epstein (University of Haifa)
• Henning Fernau (Trier University)
• Fedor Fomin (University of Bergen)
• Pierre Fraigniaud (IRIF Université Paris Cité)
• Jean Goubault-Larrecq (CNRS and ENS Paris-Saclay)
• Kristoffer Arnsfelt Hansen (Aarhus University)
• Lane Hemaspaandra (University of Rochester)
• Petr Jancar (Palacky University Olomouc)
• Christos Kapoutsis (Carnegie Mellon University in Qatar)
• Stefan Kiefer (University of Oxford)
• Ralf Klasing (CNRS, LaBRI, University of Bordeaux)
• Naoki Kobayashi (University of Tokyo)
• Barbara König (University of Duisburg-Essen)
• Martin Koutecký (Charles University, Prague)
• Rastislav Kralovic (Comenius University in Bratislava, chair)
• Tony Kucera (Masaryk University Brno, chair)
• Tobias Momke (University of Augsburg)
• Madhavan Mukund (Chennai Mathematical Institute)
• Daniel Paulusma (Durham University)
• Giovanni Pighizzini (University of Milan)
• Alexander Rabinovich (Tel Aviv University)
• Peter Rossmanith (RWTH Aachen)
• Christian Scheideler (Paderborn University)
• Sebastian Siebertz (University of Bremen)
• Martin Skoviera (Comenius University in Bratislava)
• Bettina Speckmann (TU Eindhoven)
• Paul Spirakis (University of Liverpool)
• Daniel Stefankovic (University of Rochester)
• Till Tantau (University of Lübeck)
• Takeshi Tsukada (Chiba University)
• Ugo Vaccaro (University of Salerno)
• Igor Walukiewicz (LaBRI , Université de Bordeaux)

Invited Speakers

• Wojciech Czerwiński (University of Warsaw)
• Jarkko Kari (University of Turku)
• Kasper Green Larsen (Aarhus University)
• Rupak Majumdar (Max Planck Institute for Software Systems)
• David Peleg (Weizmann Institude of Science)

Proceedings

As in previous years, MFCS 2024 proceedings is published in LIPIcs (Leibniz International Proceedings in Informatics) under an open access license: LIPIcs proceedings.

Selected articles will be invited to a special issue of Information and Computation

Important Dates

• Submission Deadline: Friday, April 26, 2024 (Anywhere on Earth)
• Notification: Monday, June 24, 2024
• Camera-ready Deadline: Friday, June 28, 2024
• Conference: August 26 — 30, 2024,

Accepted Papers

• Tim Seppelt. An Algorithmic Meta Theorem for Homomorphism Indistinguishability
• Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen and Kasper Green Larsen. Sublinear Time Shortest Path in Expander Graphs
• Václav Blažej, Dušan Knop, Jan Pokorný and Šimon Schierreich. Equitable Connected Partition and Structural Parameters Revisited: N-fold Beats Lenstra
• Jan Goedgebeur, Jorik Jooken, Karolina Okrasa, Paweł Rzążewski and Oliver Schaudt. Minimal obstructions to $C_5$-coloring in hereditary graph classes
• Lisa Marie Jaser and Jacobo Toran. Pebble Games and Algebraic Proof Systems
• Jessica Enright, Samuel Hand, Laura Larios-Jones and Kitty Meeks. Structural Parameters for Dense Temporal Graphs
• Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev, Antoine Dailly, Yan Gerard, Aurélie Lagoutte, Vincent Limouzy and Lucas Pastor. The Canadian Traveller Problem on outerplanar graphs
• Daniele D'Angeli, Emanuele Rodaro and Jan Philipp Wächter. The Freeness Problem for Automaton Semigroups
• Markus Lohrey and Julio Xochitemol. Streaming in graph products
• Rupert Hölzl, Philip Janicki, Wolfgang Merkle and Frank Stephan. Randomness versus superspeedability
• Max Bannach, Florian Chudigiewitsch and Till Tantau. On the Descriptive Complexity of Vertex Deletion Problems
• Karen Frilya Celine, Ziyuan Gao, Sanjay Jain, Ryan Lou, Frank Stephan and Guohua Wu. Quasi-Isometric Reductions Between Infinite Strings
• Arnold Beckmann and Georg Moser. On Complexity of Confluence and Church-Rosser Proofs
• Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń and Jakub Przybyło. First-Fit Coloring of Forests in Random Arrival Model
• Gang Liu and Haitao Wang. Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems
• Petr Hlineny and Jan Jedelský. H-Clique-Width and a Hereditary Analogue of Product Structure
• Guillermo Badia, Manfred Droste, Carles Noguera and Erik Paul. Logical Characterizations of Weighted Complexity Classes
• Virginia Ardévol Martínez, Romeo Rizzi, Abdallah Saffidine, Florian Sikora and Stéphane Vialette. Generalizing Roberts' characterization of unit interval graphs
• Zohair Raza Hassan. The Complexity of (P3, H)-Arrowing and Beyond
• Filippo Bonchi, Alessandro Di Giorgio and Davide Trotta. When Lawvere meets Peirce: an equational presentation of boolean hyperdoctrines
• Tesshu Hanaka, Michael Lampis, Manolis Vasilakis and Kanae Yoshiwatari. Parameterized Vertex Integrity Revisited
• Giovanni Viglietta and Giuseppe Antonio Di Luna. Efficient Computation in Congested Anonymous Dynamic Networks
• Zhen Zhang, Qilong Feng and Junyu Huang. Faster Approximation Schemes for (Constrained) k-Means with Outliers
• Hunter Chase, James Freitag and Lev Reyzin. Applications of Littlestone dimension to query learning and to compression
• Satyadev Nandakumar, Subin Pulari and Akhil S. Point-to-set Principle and Constructive Dimension Faithfulness
• Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud and Ralf Klasing. Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
• Yahia Idriss Benalioua, Nathan Lhote and Pierre-Alain Reynier. Minimizing Cost Register Automata over a Field
• Dibyayan Chakraborty, Haiko Müller, Sebastian Ordyniak, Fahad Panolan and Mateusz Rychlicki. Covering and Partitioning of Split, Chain and Cographs with Isometric Paths
• Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran and Dror Rawitz. Sparse Graphic Degree Sequences Have Planar Realizations
• Anuj Dawar and Ioannis Eleftheriadis. Preservation theorems on sparse classes revisited
• Benjamin Monmege, Julie Parreaux and Pierre-Alain Reynier. Synthesis of Robust Optimal Real-Time Systems
• Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz and Frank Sommer. On the Complexity of Community-aware Network Sparsification
• Olaf Beyersdorff, Tim Hoffmann, Kaspar Kasche and Luc Nicolas Spachmann. Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree
• Christian Ortlieb. Toward Grünbaum's Conjecture for 4-Connected Graphs
• Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin and Jean-Florent Raymond. Local certification of geometric graph classes
• Vladimirs Andrejevs, Aleksandrs Belovs and Jevgēnijs Vihrovs. Quantum algorithms for Hopcroft's problem
• Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier and Thomas Zeume. Query maintenance under batch changes with small-depth circuits
• Marta Piecyk. $C_{2k+1}$-coloring of bounded-diameter graphs
• Isolde Adler and Eva Fluck. Monotonicity of the cops and robber game for bounded depth treewidth
• Julien Grange, Fabian Vehlken, Nils Vortmeier and Thomas Zeume. Specification and Automatic Verification of Computational Reductions
• L. Sunil Chandran, Rishikesh Gajjala and Abraham Mathew Illickan. Krenn-Gu conjecture for sparse graphs
• Arnaud Casteigts, Nils Morawietz and Petra Wolf. Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs
• David Lidell, Shaun Azzopardi and Nir Piterman. A Direct Translation from LTL with Past to Deterministic Rabin Automata
• Wiktor Zuba, Grigorios Loukides, Solon Pissis and Sharma V. Thankachan. Approximate Suffix-Prefix Dictionary Queries
• Jakob Piribauer. Demonic variance and a non-determinism score for Markov decision processes
• Syamantak Das, Nikhil Kumar and Daniel Vaz. Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
• Andrew Ryzhikov and Petra Wolf. Monoids of upper triangular matrices over the Boolean semiring
• Mohammed Elaroussi, Lhouari Nourine and Simon Vilmin. Half-space separation in monophonic convexity
• Yuto Nakashima, Dominik Köppl, Mitsuru Funakoshi, Shunsuke Inenaga and Hideo Bannai. Edit and Alphabet-Ordering Sensitivity of Lex-parse
• Sourav Chakraborty, Swarnalipa Datta, Pranjal Dutta, Arijit Ghosh and Swagato Sanyal. On Fourier analysis of sparse Boolean functions over certain Abelian groups
• Avantika Agarwal, Sevag Gharibian, Venkata Koppula and Dorian Rudolph. Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction and Lower Bounds
• Jesse Beisegel, Ekkehard Köhler, Fabienne Ratajczak, Robert Scheffler and Martin Strehler. Graph Search Trees and the Intermezzo Problem
• Ulysse Léchine, Thomas Seiller and Jakob Grue Simonsen. Agafonov’s theorem for probabilistic selectors
• Édouard Bonnet, Julien Duron, John Sylvester and Viktor Zamaraev. Symmetric-Difference (Degeneracy) and Signed Tree Models
• Hsiang-Hsuan Liu and Fu-Hong Liu. Scheduling with Locality by Routing
• Ivor van der Hoog, André Nusser, Eva Rotenberg and Frank Staals. Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs
• Antonio Casares and Corto Mascle. The Complexity of Simplifying $\omega$-Automata through the Alternating Cycle Decomposition
• Nathan van Beusekom, Marc van Kreveld, Max van Mulken, Marcel Roeloffzen, Bettina Speckmann and Jules Wulms. Capturing the Shape of a Point Set With a Line Segment
• Paola Bonizzoni, Clelia De Felice, Brian Riccardi, Rocco Zaccagnino and Rosalba Zizza. Unveiling the connection between the Lyndon factorization and the canonical inverse Lyndon factorization via a border property
• Archit Chauhan, Samir Datta, Chetan Gupta and Vimal Raj Sharma. The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs
• Gang Liu and Haitao Wang. On Line-Separable Weighted Unit-Disk Coverage and Related Problems
• Niel de Beaudrap and Richard East. Simple qudit ZX~and ZH~calculi, via integrals
• Melissa Antonelli, Arnaud Durand and Juha Kontinen. A New Characterization of FAC^0 via Discrete Ordinary Differential Equations
• David Dingel, Fabian Egidy and Christian Glasser. An Oracle with no UP-Complete Sets, but NP = PSPACE
• Kristóf Bérczi, Tamás Király and Daniel Szabo. Multiway Cuts with a Choice of Representatives
• Marco Carmosino, Ronald Fagin, Neil Immerman, Phokion Kolaitis, Jonathan Lenchner and Rik Sengupta. On the Number of Quantifiers Needed to Define Boolean Functions
• Dariusz Kalociński, Luca San Mauro and Michał Wrocławski. Punctual presentability in certain classes of algebraic structures
• Yakov Shalunov. Leakage-Resilient Hardness Equivalence to Logspace Derandomization
• Jack H. Lutz and Andrei Migunov. Algorithmic Dimensions via Learning Functions
• Dhanyamol Antony, Yixin Cao, Sagartanu Pal and R B Sandeep. Switching Classes: Characterization and Computation
• Daniel Kráľ, Kristýna Pekárková and Kenny Štorgel. Twin-width of graphs on surfaces
• Zeno Bitter and Antoine Mottet. Generalized Completion Problems with Forbidden Tournaments
• Dana Fisman, Emmanuel Goldberg and Oded Zimerman. A Robust Measure on FDFAs Following1 Duo-Normalized Acceptance
• Tian Bai and Mingyu Xiao. Breaking the Barrier 2^k for Subset Feedback Vertex Set in Chordal Graphs
• Matthias Bentert, Michael R. Fellows, Petr A. Golovach, Frances A. Rosamond and Saket Saurabh. Breaking a Graph into Connected Components with Small Dominating Sets
• Susobhan Bandopadhyay, Aritra Banik, Diptapriyo Majumdar and Abhishek Sahu. Tractability of Packing Vertex-Disjoint {\sf A}-Paths under Length Constraints
• Michał Makowski. On the Complexity of the Conditional Independence Implication Problem With Bounded Cardinalities
• Alexander Rubtsov and Nikita Chudinov. Computational Model for Parsing Expression Grammars
• Harmender Gahlawat, Jan Matyas Kristan and Tomas Valla. Romeo and Juliet is EXPTIME-complete
• Liye Guo, Kasper Hagens, Cynthia Kop and Deivid Vale. Higher-Order Constrained Dependency Pairs for (Universal) Computability

Registration

The registration fee includes, among others, attendance to the lectures, coffee breaks, lunches, and the conference dinner.

Students who at the time of the conference have not yet completed their PhD qualify for the student status of the registration.

You can become an EATCS member here and immediately benefit from the reduced registration fee. The membership fee is €40 for a year (two years for students).

Conference Venue

The conference will take place at the Faculty of Mathematics, Physics and Informatics of the Comenius University in Bratislava, Mlynská dolina, 842 48 Bratislava (location on Google Maps).

The venue is located within walking distance from the following public transport stops:

• Botanická záhrada (trams 4 and 9, buses 29 and 32)
• ZOO (buses 31 and 39)

Conference Dinner

The conference dinner will take place in the Moyzes Hall, Vajanského nábrežie 12, Bratislava (location on Google Maps). It is located within a short walking distance from the public transport stop "Šafárikovo námestie" (trams 1,3,4 and buses 29,50,70).

Accommodation

A limited number of rooms have been reserved for conference participants at the following two hotels. You can make use of the keyword MFCS to book a room. Please note that the reservation lasts only until July 15, 2024, so we strongly recommend booking before then:

• Hotel SOREA Regia (close to the conference venue)
• Hotel Devín (within walking distance from the Most SNP bus stop where buses from the Vienna airport arrive)

Other hotels near the tram lines to the conference venue:

• Hotel Ibis Bratislava Centrum
• Mamaison Residence
• Arcadia Boutique Hotel

Travel Information

Reaching Bratislava from Vienna Airport

The most common way to reach Bratislava is via the Vienna International Airport, from where there are frequent regional bus connections directly to the bus stop Most SNP in the centre of Bratislava (about 45 minutes). The bus connections can be found here.

Bratislava Airport

There are also several flights to and from Bratislava Airport operated mostly by low-cost carriers. Both the city centre and the conference location can be reached from the airport by taking a bus 61 and changing to a tram 4 or 9 at Trnavské mýto.

Reaching Bratislava by Train

Bratislava main train station is connected by international trains to Prague, Berlin, Warsaw, Budapest, etc. City centre can be reached from the main train station by tram 1 or by bus 93. There is also a direct bus 32 from the train station to the bus stop Botanická záhrada near the conference venue.

Restaurants

We recommend the following restaurants located near most hotels in the city center. This selection offers a variety of cuisines, from Slovakian specialties to international favorites. This list is not exhaustive, there are many other good dining options in Bratislava.

• Slovak / Central European cuisine: Bratislava Flagship Restaurant, Dolnozemská krčma, Houdini Restaurant
• Italian: Gatto Matto Panská, Le Due Sicilie, Ristorante Italiano da Cono Zuckermandel
• Spanish: Mecheche (tapas, paella, seafood)
• Eastern Mediterranean: Arabeska bistro (arabic)
• Burgers: Be About, Urban Bistro
• Asian: Jasmin  (chinese), Wabi Sabi (japanese), Bistro Soho (thai)
• Mexican: Mezcalli Bratislava
• Indian: Red Chilli, Nivara
• Ice cream: I Nonni Cremeria, Luculus Ice Saloon

Places Worth Visiting

• Bratislava Castle
• Devín Castle
• Slavín
• The Blue Church
• Devínska Kobyla and surroundings
• Danubiana Art Museum
• Botanical Garden of the Comenius University

Contact

For any questions, please don't hesitate to contact us at mfcs2024@mfcs.sk.