Sponsors:
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:3008:50 
Registration 
Registration & Refreshments 
08:5009:00 
Opening 
09:0010:00 
Invited Talk: Joël Ouaknine 
A4 Lower bounds
B4 Quantum I 
Invited Talk: Amina Doumane 
Invited Talk: Martin Grohe 
Invited Talk: Eva Rotenberg 
10:0010:30 
Coffee Break 
10:3012: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:3014:30 
Lunch 
14:3016:00 
A2 Parametrized complexity I
B2 Concurrency 
A6 Graphs I
B6 Logics 
A8 Graphs II
B8 Language theory and algebra 
A10 CSP
B10 Models of computation 
A13 Temporal graphs
B13 Computational geometry 
16:0016:30 
Coffee Break 
Closing 
16:3018:00 
A3 Parametrized complexity II
B3 Spatial and temporal logics

16:3017:30 Invited Talk: Barna Saha 
Social Program & Conference Dinner 
A11 Strings
B11 Automata 

18:00 Welcome reception 
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 
Opening 
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 
Lunch 
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 vertexkernel for Trivially Perfect Editing 
A. Cesco, R. Gorrieri A Decidable Equivalence for a Turingcomplete, 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 Codegeneracy and cotreewidth: Using the complement to solve dense instances 
M. Fortin, L. B. Kuijer, P. Totzke, M. Zimmermann HyperLTL Satisfiability is Sigma_1^1complete, HyperCTL* Satisfiability is Sigma_1^2complete 

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 
18:00 
Welcome Reception 

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 BlackBox Hypotheses and Lower Bounds 
A. Glos, M. Kokainis, R. Mori, J. Vihrovs Quantum speedups for dynamic programming on ndimensional 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 SmallDepth Quantum Circuits 

M. Kaminski, I. E. Shparlinski Sets of linear forms which are hard to compute 
R. Vilmart Quantum MultipleValued 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 PBSdiagrams 
12:30  14:30 
Lunch 
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 firstorder logic 

D. Bilò, S. Cohen, T. Friedrich, M. Schirneck SpaceEfficient FaultTolerant Diameter Oracles 
D. Hausmann, S. Milius, L. Schröder A LinearTime Nominal muCalculus 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 MuCalculus 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 NonAxiomatizability 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 HFree 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 SecondOrder Holonomic Sequences 

E. Allender, A. Chauhan, S. Datta DepthFirst Search in Directed Graphs, Revisited 
U. Dal Lago, R. Kahle, I. Oitavem A RecursionTheoretic Characterization of the Probabilistic Class PP 
12:30  14:30 
Lunch 
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 chordallike graphs 
P. Jancar, J. Sima Simplest NonRegular Deterministic ContextFree Language 

C. Figueiredo, A. Melo, F. Oliveira, A. Silva Maximum cut on interval graphs of interval count four is NPcomplete 
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 Semiedges: 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 
Social Event & Conference Dinner 

Thursday, August 26 
08:30  09:00 
Registration & Refreshments 
09:00  10:00 
Invited Talk: Martin Grohe A Deep Dive into the WeisfeilerLeman 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éneauTabot 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 
Lunch 
14:30  16:00 
A10  CSP (Chair: ) 
B10  Models of computation (Chair: Filippo Bonchi) 

S. Butti, V. Dalmau Fractional homomorphism, WeisfeilerLeman invariance, and the SheraliAdams 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 gaugeinvariant 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 omegaautomata 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 originclose topdown 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 ParetoEfficient Allocations via Swaps on a Social Network 
C. Haase, A. Mansutti On deciding linear arithmetic constraints over padic 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 PseudoSkolem 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 
Lunch 
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 PSPACEcomplete 

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 
