46th International Symposium on

Mathematical Foundations of Computer Science

August 23-27, 2021, Tallinn (Estonia)


MFCS 2021 is organized in cooperation with EATCS

IOS Press, the publisher of Fundamenta Informaticae is the MFCS 2021 media partner


Conference Program

Program Overview

All times are Tallinn local time (UTC+3).

Monday Tuesday Wednesday Thursday Friday
time August 23 August 24 August 25 August 26 August 27
08:30-08:50 Registration Registration & Refreshments
09:00-10:00 Invited Talk:
A4 Lower bounds

B4 Quantum I
Invited Talk:
Invited Talk:
Invited Talk:
10:00-10:30 Coffee Break
10:30-12:30 A1 Complexity I

B1 Categories
and Types
A5 Complexity II

B5 Quantum II
A7 Graph algorithms

B7 Dynamical,
probabilistic and
stochastic systems
A9 Graphs, algebras
and combinatorics

B9 Automata I
A12 Distributed and
parallel algorithms

B12 Decidability
12:30-14:30 Lunch
14:30-16:00 A2 Parametrized
complexity I

B2 Concurrency
A6 Graphs I

B6 Logics
A8 Graphs II

B8 Language theory
and algebra

B10 Models of
A13 Temporal graphs

B13 Computational
16:00-16:30 Coffee Break
16:30-18:00 A3 Parametrized
complexity II

B3 Spatial and
temporal logics
Invited Talk:
A11 Strings

B11 Automata


NB: To ensure the best hybrid experience, the exact ordering of talks in each session will be announced shortly before the conference.

Monday, August 23
08:30 - 08:50
Registration & Refreshments
08:50 - 09:00
09:00 - 10:00
Invited Talk:
Joël Ouaknine
Holonomic Techniques, Periods, and Decision Problems
(Chair: Filippo Bonchi)
10:00 - 10:30
Coffee Break
10:30 - 12:30 A1 - Complexity (Chair: Petra Wolf) B1 - Categories and Types (Chair: Edward Morehouse)
S. Nandakumar, S. Pulari
Ergodic Theorems and converses for PSPACE functions
M. Ikebuchi
A Homological Condition on Equational Unifiability
P. Hubáček, J. Václavek
On Search Complexity of Discrete Logarithm
D. Trotta, M. Spadetto, V. de Paiva
The Gödel fibration
S. Chaubal, A. Gal
Diameter versus Certificate Complexity of Boolean Functions
A. Bhaskar, R. Kaarsgaard
Graph Traversals as Universal Constructions
M.A. Khamis, R. Curtin, S. Im, B. Moseley, H. Ngo, K. Pruhsand, A. Samadian
An Approximation Algorithm for the Matrix Tree Multiplication Problem
N. Kraus, C. Xuand, F. Nordvall Forsberg
Connecting Constructive Notions of Ordinals in Homotopy Type Theory
12:30 - 14:30
14:30 - 16:00 A2 - Parametrized complexity I (Chair: Jevgenijs Vihrovs) B2 - Concurrency (Chair: Pawel Sobocinski)
S. Bandyapadhyay, F. Fomin, P. Golovach, K. Simonov
Parameterized Complexity of Feature Selection for Categorical Data Clustering
V. Arvind, A. Chatterjee, R. Datta, P. Mukhopadhyay
Equivalence Testing of Weighted Automata over Partially Commutative Monoids
N. Peyerimhoff, M. Roth, J. Schmitt, J. Stix, A. Vdovina
Parameterized (Modular) Counting and Cayley Graph Expanders
S. Tsampas, C. Williams, A. Nuyts, D. Devriese, F. Piessens
Abstract congruence criteria for weak bisimilarity
M. Dumas, A. Perez, I. Todinca
A cubic vertex-kernel for Trivially Perfect Editing
A. Cesco, R. Gorrieri
A Decidable Equivalence for a Turing-complete, Distributed Model of Computation
16:00 - 16:30
Coffee Break
16:30 - 18:00 A3 - Parametrized complexity II (Chair: Silvia Butti) B3 - Spatial and temporal logics (Chair: Corto Mascle)
N. Mählmann, S. Siebertz, A. Vigny
Recursive Backdoors for SAT
S. Linker, F. Papacchini, M. Sevegnani
Finite Models for a Spatial Logic with Discrete and Topological Path Operators
G. Duarte, M. De Oliveira Oliveira, U. Souza
Co-degeneracy and co-treewidth: Using the complement to solve dense instances
M. Fortin, L. B. Kuijer, P. Totzke, M. Zimmermann
HyperLTL Satisfiability is Sigma_1^1-complete, HyperCTL* Satisfiability is Sigma_1^2-complete
B. M. P. Jansen, S. K. Roy, M. Wlodarczyk
On the Hardness of Compressing Weights
Achim Blumensath, Jakub Lédl
ω-Forest Algebras and Temporal Logics

Tuesday, August 24
08:30 - 09:00
Registration & Refreshments
09:00 - 10:00 A4 - Lower bounds (Chair: Simon Puglisi) B4 - Quantum I (Chair: Pawel Sobocinski)
B. Chapman, R. Williams
Black-Box Hypotheses and Lower Bounds
A. Glos, M. Kokainis, R. Mori, J. Vihrovs
Quantum speedups for dynamic programming on n-dimensional lattice graphs
R. Ferens, M. Szykuła, V. Vorel
Lower Bounds on Avoiding Thresholds
D. Huey, C. Lim, H. Klauck
The Power of One Clean Qubit in Communication Complexity
10:00 - 10:30
Coffee Break
10:30 - 12:30 A5 - Complexity II (Chair: George Kenison) B5 - Quantum II (Chair: Amar Hadzihasanovic)
J. D'Costa, E. Lefaucheux, E. Neumann, J. Ouaknine, J. Worrell
On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
K. Chardonnet, B. Valiron, R. Vilmart
Geometry of Interaction for ZX Diagrams
M. A. Deppert, K. Jansen, K.-M. Klein
Fuzzy Simultaneous Congruences
S. Hiraharaand, F. Le Gall
Test of Quantumness with Small-Depth Quantum Circuits
M. Kaminski, I. E. Shparlinski
Sets of linear forms which are hard to compute
R. Vilmart
Quantum Multiple-Valued Decision Diagrams in Graphical Calculi
B. Kivva
Improved upper bounds for the rigidity of Kronecker products
C. Branciard, A. Clément, M. Mhallaand, S. Perdrix
Coherent control and distinguishability of quantum channels via PBS-diagrams
12:30 - 14:30
14:30 - 16:00 A6 - Graphs I (Chair: Andras Papp) B6 - Logics (Chair: Niccolo Veltri)
N.S. Narayanaswamy, D. Peleg, V. Ramamoorthi, K. Choudhary, A. Cohen
Budgeted Dominating Sets in Uncertain Graphs
R. Jaakkola
Ordered fragments of first-order logic
D. Bilò, S. Cohen, T. Friedrich, M. Schirneck
Space-Efficient Fault-Tolerant Diameter Oracles
D. Hausmann, S. Milius, L. Schröder
A Linear-Time Nominal mu-Calculus with Name Allocation
M. Briański, S. Felsner,J. Hodor,P. Micek
Reconfiguring independent sets on interval graph
F. Bruse, M. Sälzer, M. Lange
Finite Convergence of Mu-Calculus Fixpoints on Genuinely Infinite Structures
16:00 - 16:30
Coffee Break
16:30 - 17:30
Invited Talk:
Barna Saha
Sublinear Algorithms for Edit Distance
(Chair: Simon J. Puglisi)

Wednesday, August 25
08:30 - 09:00
Registration & Refreshments
09:00 - 10:00
Invited Talk:
Amina Doumane
Non-Axiomatizability of the Equational Theories of Positive Relation Algebra
(Chair: Filippo Bonchi)
10:00 - 10:30
Coffee Break
10:30 - 12:30 A7 - Graph algorithms (Chair: Armin Weiss) B7 - Dynamical, probabilistic and stochastic systems (Chair: M. Skrzypczak)
G. Ducoffe
Isometric embeddings in trees and their use in distance problems
P. Belland, P. Semukhin
Decision Questions for Probabilistic Automata on Small Alphabets
G. Paesani, P. Rzążewski
Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
D. Auger, X. Badin de Montjoye, Y. Strozecki
Generic Strategy Improvement Method for Simple Stochastic Games
J. Racicot, D. Pankratov, H. Harutyunyan
Online Domination: The Value of Getting to Know All your Neighbors
G. Kenison, O. Klurman, E. Lefaucheux, O. Klurman, F. Luca, P. Moree, J. Ouaknine, M. Whiteland, J. Worrell
On Positivity and Minimality for Second-Order Holonomic Sequences
E. Allender, A. Chauhan, S. Datta
Depth-First Search in Directed Graphs, Revisited
U. Dal Lago, R. Kahle, I. Oitavem
A Recursion-Theoretic Characterization of the Probabilistic Class PP
12:30 - 14:30
14:30 - 16:00 A8 - Graphs II (Chair: Eric Allender) B8 - Language theory and algebra (Chair: )
G. Ducoffe
On computing the maximum and average distances for some chordal-like graphs
P. Jancar, J. Sima
Simplest Non-Regular Deterministic Context-Free Language
C. Figueiredo, A. Melo, F. Oliveira, A. Silva
Maximum cut on interval graphs of interval count four is NP-complete
H. Tamm
Boolean Automata and Atoms of Regular Languages
Jan Bok, Jiří Fiala, Petr Hliněný, Nikola Jedličková, Jan Kratochvíl
Computational Complexity of Covering Multigraphs with Semi-edges: Small Cases
Nathan Grosshans
A Note on the Join of Varieties of Monoids With LI
16:00 - 16:30
Coffee Break
16:30 - 22:00

Thursday, August 26
08:30 - 09:00
Registration & Refreshments
09:00 - 10:00
Invited Talk:
Martin Grohe
A Deep Dive into the Weisfeiler-Leman Algorithm
(Chair: Simon J. Puglisi)
10:00 - 10:30
Coffee Break
10:30 - 12:30 A9 - Graphs, Algebras and Combinatorics (Chair: Pawel Sobocinski) B9 - Automata I (Chair: Peter Jancar)
E. Arrighi, H. Fernau, M. De Oliveira Oliveira, P. Wolf
Order Reconfiguration under Width Constraints
G. Douéneau-Tabot
Pebble transducers with unary outputs
A. Dawar, D. Vagnozzi
On the relative power of linear algebraic approximations of graph isomorphism
B. Abu Radi, O. Leshkowitz, O. Kupferman
A Hierarchy of Nondeterminism
A. Doumane
Graph characterization of the universal theory of relations
S. Guha, I. Jecker, K. Lehtinen, M. Zimmermann
A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
G. Gutin, A. Yeo
Perfect Forests in Graphs and Their Extensions
R. Myers, H. Urbat
Syntactic Minimization of Nondeterministic Finite Automata
12:30 - 12:40
MFCS 2022 Presentation
12:40 - 14:30
14:30 - 16:00 A10 - CSP (Chair: ) B10 - Models of computation (Chair: Filippo Bonchi)
S. Butti, V. Dalmau
Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the Constraint Satisfaction Problem
Y. Géran, B. Laboureix, C. Mascle , V. D. Richard
Keyboards as a New Model of Computation
A. P. Bharathi, M. Mastrolilli
Ideal Membership Problem for Boolean Minority and Dual Discriminator
K. Nakano
Idempotent Turing Machines
L. Barto, K. Asimi
Finitely Tractable Promise Constraint Satisfaction Problems
P. Arrighi, M. Costes, N. Eon
Universal gauge-invariant cellular automata
16:00 - 16:30
Coffee Break
16:30 - 18:00 A11 - Strings (Chair: Simon Puglisi) B11 - Automata (Chair: Henning Urbat)
Vít Jelínek, Michal Opler, Jakub Pekárek
Griddings of permutations and the hardness of pattern matching
Leon Bohn, Christof Löding
Constructing deterministic omega-automata from examples by an extension of the RPNI algorithm
P. Gawrychowski, F. Manea, S. Siemer
Matching Patterns with Variables under Hamming Distance
S. Winter
Decision problems for origin-close top-down tree transducers
H. Gruber, M. Holzer
Optimal Regular Expressions for Palindromes of Given Length
D. Niwiński, M. Skrzypczak
On guidable index of tree automata

Friday, August 27
08:30 - 09:00
Registration & Refreshments
09:00 - 10:00
Invited Talk:
Eva Rotenberg
On Dynamic Graphs
(Chair: Simon J. Puglisi)
10:00 - 10:30
Coffee Break
10:30 - 12:30 A12 - Distributed and parallel algorithms (Chair: Amar Hadzihasanovic) B12 - Decidability (Chair: Florian Luca)
F. Li, X. Zheng
Maximum Votes Pareto-Efficient Allocations via Swaps on a Social Network
C. Haase, A. Mansutti
On deciding linear arithmetic constraints over p-adic integers for all primes
S. Datta, K. Jaiswal
Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles
J. D’Costa, T. Karimov, R. Majumdar, J. Ouaknine, M. Salamati, S. Soudjani, J. Worrell
The Pseudo-Skolem Problem is Decidable
P. A. Papp, R. Wattenhofer
Stabilization Bounds for Influence Propagation from a Random Initial State
P. Baldan, A. Carraro, T. Padoan
(Un)Decidability for History Preserving True Concurrent Logics
C. Mattes, A. Weiß
Parallel algorithms for power circuits and the word problem of the Baumslag group
12:30 - 14:30
14:30 - 16:00 A13 - Temporal graphs (Chair: Nidia Obscura Acosta) B13 - Computational geometry (Chair: Ed Morehouse)
H. Molter, M. Renken, P. Zschoche
Temporal Reachability Minimization: Delaying vs. Deleting
P. Haghighatkhah, W. Meulemans, B. Speckmann, J. Urhausen, K. Verbeek
Obstructing Classification via Projection
N. Morawietz, P. Wolf
A Timecop's Chase Around the Table
K. Buchin, M. Hagedoorn, I. Kostitsyna, M. van Mulken
Dots & Boxes is PSPACE-complete
G. Mertzios, H. Molter, M. Renken, P. Spirakis, P. Zschoche
The Complexity of Transitively Orienting Temporal Graphs
K. Buchin, M. Löffler, A. Popov, M. Roeloffzen
Uncertain Curve Simplification

Important Dates

Camera-ready copies due:    July 9th, 2021   
Conference dates: August 23–27, 2021

Contact: Pawel Sobocinski (sobocinski@gmail.com)