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:30-08:50 |
Registration |
Registration & Refreshments |
| 08:50-09:00 |
Opening |
| 09:00-10: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: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 |
A10 CSP
B10 Models of
computation |
A13 Temporal graphs
B13 Computational
geometry |
| 16:00-16:30 |
Coffee Break |
Closing |
| 16:30-18:00 |
A3 Parametrized
complexity II
B3 Spatial and
temporal logics
|
16:30-17: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 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 |
| 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
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 |
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 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 |
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 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 |
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 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 |
Lunch |
| 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 |
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 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 |
|