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


Accepted Papers

  • Guillaume Ducoffe. On computing the maximum and average distances for some chordal-like graphs
  • Stelios Tsampas, Christian Williams, Andreas Nuyts, Dominique Devriese and Frank Piessens. Abstract congruence criteria for weak bisimilarity
  • Samir Datta and Kishlaya Jaiswal. Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles
  • Amina Doumane. Graph characterization of the universal theory of relations
  • Satyadev Nandakumar and Subin Pulari. Ergodic Theorems and converses for PSPACE functions
  • Michael Kaminski and Igor E. Shparlinski. Sets of linear forms which are hard to compute
  • Gaëtan Douéneau-Tabot. Pebble transducers with unary outputs
  • Achim Blumensath and Jakub Lédl. ω-Forest Algebras and Temporal Logics
  • Guillaume Ducoffe. Isometric embeddings in trees and their use in distance problems
  • Reijo Jaakkola. Ordered fragments of first-order logic
  • Kostia Chardonnet, Benoît Valiron and Renaud Vilmart. Geometry of Interaction for ZX Diagrams
  • Jan Bok, Jiří Fiala, Petr Hliněný, Nikola Jedličková and Jan Kratochvíl. Computational Complexity of Covering Multigraphs with Semi-edges: Small Cases
  • Caroline Mattes and Armin Weiß. Parallel algorithms for power circuits and the word problem of the Baumslag group
  • Shuichi Hirahara and Francois Le Gall. Test of Quantumness with Small-Depth Quantum Circuits
  • Giacomo Paesani, Daniel Paulusma and Paweł Rzążewski. Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
  • Sayan Bandyapadhyay, Fedor Fomin, Petr Golovach and Kirill Simonov. Parameterized Complexity of Feature Selection for Categorical Data Clustering
  • Max A. Deppert, Klaus Jansen and Kim-Manuel Klein. Fuzzy Simultaneous Congruences
  • Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix and Alina Vdovina. Parameterized (Modular) Counting and Cayley Graph Expanders
  • Gregory Gutin and Anders Yeo. Perfect Forests in Graphs and Their Extensions
  • Robert Ferens, Marek Szykuła and Vojtěch Vorel. Lower Bounds on Avoiding Thresholds
  • Mirai Ikebuchi. A Homological Condition on Equational Unifiability
  • Pantea Haghighatkhah, Wouter Meulemans, Bettina Speckmann, Jérôme Urhausen and Kevin Verbeek. Obstructing Classification via Projection
  • Mahmoud Abo Khamis, Ryan Curtin, Sungjin Im, Benjamin Moseley, Hung Ngo, Kirk Pruhs and Alireza Samadian. An Approximation Algorithm for the Matrix Tree Multiplication Problem
  • Yoan Géran, Bastien Laboureix, Corto Mascle and Valentin D. Richard. Keyboards as a New Model of Computation
  • Ugo Dal Lago, Reinhard Kahle and Isabel Oitavem. A Recursion-Theoretic Characterization of the Probabilistic Class PP
  • Celina Figueiredo, Alexsander Melo, Fabiano Oliveira and Ana Silva. Maximum cut on interval graphs of interval count four is NP-complete
  • Keisuke Nakano. Idempotent Turing Machines
  • Renaud Vilmart. Quantum Multiple-Valued Decision Diagrams in Graphical Calculi
  • Maël Dumas, Anthony Perez and Ioan Todinca. A cubic vertex-kernel for Trivially Perfect Editing
  • Siddharth Bhaskar and Robin Kaarsgaard. Graph Traversals as Universal Constructions
  • Nathan Grosshans. A Note on the Join of Varieties of Monoids With LI
  • Paul Bell and Pavel Semukhin. Decision Questions for Probabilistic Automata on Small Alphabets
  • Davide Trotta, Matteo Spadetto and Valeria de Paiva. The Gödel fibration
  • Nikolas Mählmann, Sebastian Siebertz and Alexandre Vigny. Recursive Backdoors for SAT
  • David Auger, Xavier Badin de Montjoye and Yann Strozecki. A Generic Strategy Improvement Method for Simple Stochastic Games
  • Bader Abu Radi, Ofer Leshkowitz and Orna Kupferman. A Hierarchy of Nondeterminism
  • Nicolai Kraus, Chuangjie Xu and Fredrik Nordvall Forsberg. Connecting Constructive Notions of Ordinals in Homotopy Type Theory
  • Jesse Racicot, Denis Pankratov and Hovhannes Harutyunyan. Online Domination: The Value of Getting to Know All your Neighbors
  • Eric Allender, Archit Chauhan and Samir Datta. Depth-First Search in Directed Graphs, Revisited
  • Emmanuel Arrighi, Henning Fernau, Mateus De Oliveira Oliveira and Petra Wolf. Order Reconfiguration under Width Constraints
  • Anuj Dawar and Danny Vagnozzi. On the relative power of linear algebraic approximations of graph isomorphism
  • Bohdan Kivva. Improved upper bounds for the rigidity of Kronecker products
  • Pál András Papp and Roger Wattenhofer. Stabilization Bounds for Influence Propagation from a Random Initial State
  • Libor Barto and Kristina Asimi. Finitely Tractable Promise Constraint Satisfaction Problems
  • George Mertzios, Hendrik Molter, Malte Renken, Paul Spirakis and Philipp Zschoche. The Complexity of Transitively Orienting Temporal Graphs
  • Bart M. P. Jansen, Shivesh K. Roy and Michal Wlodarczyk. On the Hardness of Compressing Weights
  • Hermann Gruber and Markus Holzer. Optimal Regular Expressions for Palindromes of Given Length
  • Debbie Huey Chih Lim and Hartmut Klauck. The Power of One Clean Qubit in Communication Complexity
  • Hendrik Molter, Malte Renken and Philipp Zschoche. Temporal Reachability Minimization: Delaying vs. Deleting
  • Robert Myers and Henning Urbat. Syntactic Minimization of Nondeterministic Finite Automata
  • Pavel Hubáček and Jan Václavek. On Search Complexity of Discrete Logarithm
  • Sarah Winter. Decision problems for origin-close top-down tree transducers
  • Damian Niwiński and Michał Skrzypczak. On guidable index of tree automata
  • Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna and Max van Mulken. Dots & Boxes is PSPACE-complete
  • Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen and Martin Zimmermann. A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
  • Kevin Buchin, Maarten Löffler, Aleksandr Popov and Marcel Roeloffzen. Uncertain Curve Simplification
  • Arnaldo Cesco and Roberto Gorrieri. A Decidable Equivalence for a Turing-complete, Distributed Model of Computation
  • Leon Bohn and Christof Löding. Constructing deterministic omega-automata from examples by an extension of the RPNI algorithm
  • Florian Bruse, Marco Sälzer and Martin Lange. Finite Convergence of Mu-Calculus Fixpoints on Genuinely Infinite Structures
  • Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joel Ouaknine and James Worrell. On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
  • Pawel Gawrychowski, Florin Manea and Stefan Siemer. Matching Patterns with Variables under Hamming Distance
  • V. Arvind, Abhranil Chatterjee, Rajit Datta and Partha Mukhopadhyay. Equivalence Testing of Weighted Automata over Partially Commutative Monoids
  • Petr Jancar and Jiri Sima. Simplest Non-Regular Deterministic Context-Free Language
  • Marcin Briański, Stefan Felsner, Jędrzej Hodor and Piotr Micek. Reconfiguring independent sets on interval graph
  • George Kenison, Oleksiy Klurman, Engel Lefaucheux, Florian Luca, Pieter Moree, Joel Ouaknine, Markus Whiteland and James Worrell. On Positivity and Minimality for Second-Order Holonomic Sequences
  • Christoph Haase and Alessio Mansutti. On deciding linear arithmetic constraints over $p$-adic integers for all primes
  • Marie Fortin, Louwe B. Kuijer, Patrick Totzke and Martin Zimmermann. HyperLTL Satisfiability is Sigma_1^1-complete, HyperCTL* Satisfiability is Sigma_1^2-complete
  • Hellis Tamm. Boolean Automata and Atoms of Regular Languages
  • Paolo Baldan, Alberto Carraro and Tommaso Padoan. (Un)Decidability for History Preserving True Concurrent Logics
  • Gabriel Duarte, Mateus De Oliveira Oliveira and Uéverton Souza. Co-degeneracy and co-treewidth: Using the complement to solve dense instances
  • Brynmor Chapman and Ryan Williams. Black-Box Hypotheses and Lower Bounds
  • Nils Morawietz and Petra Wolf. A Timecop's Chase Around the Table
  • Vít Jelínek, Michal Opler and Jakub Pekárek. Griddings of permutations and the hardness of pattern matching
  • Siddhesh Chaubal and Anna Gal. Diameter versus Certificate Complexity of Boolean Functions
  • Daniel Hausmann, Stefan Milius and Lutz Schröder. A Linear-Time Nominal mu-Calculus with Name Allocation
  • Sven Linker, Fabio Papacchini and Michele Sevegnani. Finite Models for a Spatial Logic with Discrete and Topological Path Operators
  • N.S. Narayanaswamy, David Peleg, Vijayaragunathan Ramamoorthi, Keerti Choudhary and Avi Cohen. Budgeted Dominating Sets in Uncertain Graphs
  • Cyril Branciard, Alexandre Clément, Mehdi Mhalla and Simon Perdrix. Coherent control and distinguishability of quantum channels via PBS-diagrams
  • Pablo Arrighi, Marin Costes and Nathanaël Eon. Universal gauge-invariant cellular automata
  • Arpitha Prasad Bharathi and Monaldo Mastrolilli. Ideal Membership Problem for Boolean Minority and Dual Discriminator
  • Adam Glos, Martins Kokainis, Ryuhei Mori and Jevgēnijs Vihrovs. Quantum speedups for dynamic programming on n-dimensional lattice graphs
  • Silvia Butti and Víctor Dalmau. Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the Constraint Satisfaction Problem
  • Davide Bilò, Sarel Cohen, Tobias Friedrich and Martin Schirneck. Space-Efficient Fault-Tolerant Diameter Oracles
  • Fu Li and Xiong Zheng. Maximum Votes Pareto-Efficient Allocations via Swaps on a Social Network

Important Dates

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

Contact: Pawel Sobocinski (sobocinski@gmail.com)