Portal - MFCS 2021

MFCS 2021	August 23-27, 2021, Tallinn, Estonia
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) Filippo Bonchi and Simon J. Puglisi (Eds.)
ISBN 978-3-95977-201-3, LIPICS Vol. 202	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 29 MB)
Search Publication Server

Authors

Badin de Montjoye, Xavier

de Figueiredo, Celina M. H.

de Melo, Alexsander A.

de Oliveira Oliveira, Mateus

de Paiva, Valeria

Deppert, Max A.

Devriese, Dominique

Douéneau-Tabot, Gaëtan

Haghighatkhah, Pantea

Harutyunyan, Hovhannes A.

Nordvall Forsberg, Fredrik

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Bonchi, Filippo ; Puglisi, Simon J.

Abstract | Document (566 KB) | BibTeX

Non-Axiomatizability of the Equational Theories of Positive Relation Algebras (Invited Talk)

Authors: Doumane, Amina

Abstract | Document (268 KB) | BibTeX

A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk)

Authors: Grohe, Martin

Abstract | Document (373 KB) | BibTeX

Holonomic Techniques, Periods, and Decision Problems (Invited Talk)

Authors: Ouaknine, Joël

Abstract | Document (372 KB) | BibTeX

On Dynamic Graphs (Invited Talk)

Authors: Rotenberg, Eva

Abstract | Document (337 KB) | BibTeX

Sublinear Algorithms for Edit Distance (Invited Talk)

Authors: Saha, Barna

Abstract | Document (273 KB) | BibTeX

An Approximation Algorithm for the Matrix Tree Multiplication Problem

Authors: Abo-Khamis, Mahmoud ; Curtin, Ryan ; Im, Sungjin ; Moseley, Benjamin ; Ngo, Hung ; Pruhs, Kirk ; Samadian, Alireza

Abstract | Document (685 KB) | BibTeX

Depth-First Search in Directed Planar Graphs, Revisited

Authors: Allender, Eric ; Chauhan, Archit ; Datta, Samir

Abstract | Document (964 KB) | BibTeX

Order Reconfiguration Under Width Constraints

Authors: Arrighi, Emmanuel ; Fernau, Henning ; de Oliveira Oliveira, Mateus ; Wolf, Petra

Abstract | Document (817 KB) | BibTeX

Universal Gauge-Invariant Cellular Automata

Authors: Arrighi, Pablo ; Costes, Marin ; Eon, Nathanaël

Abstract | Document (721 KB) | BibTeX

Equivalence Testing of Weighted Automata over Partially Commutative Monoids

Authors: Arvind, V. ; Chatterjee, Abhranil ; Datta, Rajit ; Mukhopadhyay, Partha

Abstract | Document (691 KB) | BibTeX

Finitely Tractable Promise Constraint Satisfaction Problems

Authors: Asimi, Kristina ; Barto, Libor

Abstract | Document (767 KB) | BibTeX

A Generic Strategy Improvement Method for Simple Stochastic Games

Authors: Auger, David ; Badin de Montjoye, Xavier ; Strozecki, Yann

Abstract | Document (785 KB) | BibTeX

(Un)Decidability for History Preserving True Concurrent Logics

Authors: Baldan, Paolo ; Carraro, Alberto ; Padoan, Tommaso

Abstract | Document (840 KB) | BibTeX

Parameterized Complexity of Feature Selection for Categorical Data Clustering

Authors: Bandyapadhyay, Sayan ; Fomin, Fedor V. ; Golovach, Petr A. ; Simonov, Kirill

Abstract | Document (812 KB) | BibTeX

Decision Questions for Probabilistic Automata on Small Alphabets

Authors: Bell, Paul C. ; Semukhin, Pavel

Abstract | Document (730 KB) | BibTeX

Ideal Membership Problem for Boolean Minority and Dual Discriminator

Authors: Bharathi, Arpitha P. ; Mastrolilli, Monaldo

Abstract | Document (934 KB) | BibTeX

Graph Traversals as Universal Constructions

Authors: Bhaskar, Siddharth ; Kaarsgaard, Robin

Abstract | Document (819 KB) | BibTeX

Space-Efficient Fault-Tolerant Diameter Oracles

Authors: Bilò, Davide ; Cohen, Sarel ; Friedrich, Tobias ; Schirneck, Martin

Abstract | Document (825 KB) | BibTeX

ω-Forest Algebras and Temporal Logics

Authors: Blumensath, Achim ; Lédl, Jakub

Abstract | Document (674 KB) | BibTeX

Constructing Deterministic ω-Automata from Examples by an Extension of the RPNI Algorithm

Authors: Bohn, León ; Löding, Christof

Abstract | Document (869 KB) | BibTeX

Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases

Authors: Bok, Jan ; Fiala, Jiří ; Hliněný, Petr ; Jedličková, Nikola ; Kratochvíl, Jan

Abstract | Document (879 KB) | BibTeX

Coherent Control and Distinguishability of Quantum Channels via PBS-Diagrams

Authors: Branciard, Cyril ; Clément, Alexandre ; Mhalla, Mehdi ; Perdrix, Simon

Abstract | Document (886 KB) | BibTeX

Reconfiguring Independent Sets on Interval Graphs

Authors: Briański, Marcin ; Felsner, Stefan ; Hodor, Jędrzej ; Micek, Piotr

Abstract | Document (936 KB) | BibTeX

Finite Convergence of μ-Calculus Fixpoints on Genuinely Infinite Structures

Authors: Bruse, Florian ; Sälzer, Marco ; Lange, Martin

Abstract | Document (696 KB) | BibTeX

Dots & Boxes Is PSPACE-Complete

Authors: Buchin, Kevin ; Hagedoorn, Mart ; Kostitsyna, Irina ; van Mulken, Max

Abstract | Document (1,410 KB) | BibTeX

Uncertain Curve Simplification

Authors: Buchin, Kevin ; Löffler, Maarten ; Popov, Aleksandr ; Roeloffzen, Marcel

Abstract | Document (975 KB) | BibTeX

Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem

Authors: Butti, Silvia ; Dalmau, Víctor

Abstract | Document (906 KB) | BibTeX

A Decidable Equivalence for a Turing-Complete, Distributed Model of Computation

Authors: Cesco, Arnaldo ; Gorrieri, Roberto

Abstract | Document (723 KB) | BibTeX

Black-Box Hypotheses and Lower Bounds

Authors: Chapman, Brynmor K. ; Williams, R. Ryan

Abstract | Document (916 KB) | BibTeX

Geometry of Interaction for ZX-Diagrams

Authors: Chardonnet, Kostia ; Valiron, Benoît ; Vilmart, Renaud

Abstract | Document (791 KB) | BibTeX

Diameter Versus Certificate Complexity of Boolean Functions

Authors: Chaubal, Siddhesh ; Gál, Anna

Abstract | Document (764 KB) | BibTeX

Budgeted Dominating Sets in Uncertain Graphs

Authors: Choudhary, Keerti ; Cohen, Avi ; Narayanaswamy, N. S. ; Peleg, David ; Vijayaragunathan, R.

Abstract | Document (962 KB) | BibTeX

On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets

Authors: D'Costa, Julian ; Lefaucheux, Engel ; Neumann, Eike ; Ouaknine, Joël ; Worrell, James

Abstract | Document (789 KB) | BibTeX

The Pseudo-Skolem Problem is Decidable

Authors: D'Costa, Julian ; Karimov, Toghrul ; Majumdar, Rupak ; Ouaknine, Joël ; Salamati, Mahmoud ; Soudjani, Sadegh ; Worrell, James

Abstract | Document (822 KB) | BibTeX

A Recursion-Theoretic Characterization of the Probabilistic Class PP

Authors: Dal Lago, Ugo ; Kahle, Reinhard ; Oitavem, Isabel

Abstract | Document (704 KB) | BibTeX

Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles

Authors: Datta, Samir ; Jaiswal, Kishlaya

Abstract | Document (765 KB) | BibTeX

On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism

Authors: Dawar, Anuj ; Vagnozzi, Danny

Abstract | Document (819 KB) | BibTeX

Maximum Cut on Interval Graphs of Interval Count Four Is NP-Complete

Authors: de Figueiredo, Celina M. H. ; de Melo, Alexsander A. ; Oliveira, Fabiano S. ; Silva, Ana

Abstract | Document (915 KB) | BibTeX

Fuzzy Simultaneous Congruences

Authors: Deppert, Max A. ; Jansen, Klaus ; Klein, Kim-Manuel

Abstract | Document (806 KB) | BibTeX

Pebble Transducers with Unary Output

Authors: Douéneau-Tabot, Gaëtan

Abstract | Document (854 KB) | BibTeX

Graph Characterization of the Universal Theory of Relations

Authors: Doumane, Amina

Abstract | Document (700 KB) | BibTeX

Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances

Authors: Duarte, Gabriel L. ; de Oliveira Oliveira, Mateus ; Souza, Uéverton S.

Abstract | Document (773 KB) | BibTeX

Isometric Embeddings in Trees and Their Use in Distance Problems

Authors: Ducoffe, Guillaume

Abstract | Document (834 KB) | BibTeX

On Computing the Average Distance for Some Chordal-Like Graphs

Authors: Ducoffe, Guillaume

Abstract | Document (808 KB) | BibTeX

A Cubic Vertex-Kernel for Trivially Perfect Editing

Authors: Dumas, Maël ; Perez, Anthony ; Todinca, Ioan

Abstract | Document (766 KB) | BibTeX

Lower Bounds on Avoiding Thresholds

Authors: Ferens, Robert ; Szykuła, Marek ; Vorel, Vojtěch

Abstract | Document (692 KB) | BibTeX

HyperLTL Satisfiability Is Σ₁¹-Complete, HyperCTL* Satisfiability Is Σ₁²-Complete

Authors: Fortin, Marie ; Kuijer, Louwe B. ; Totzke, Patrick ; Zimmermann, Martin

Abstract | Document (860 KB) | BibTeX

Matching Patterns with Variables Under Hamming Distance

Authors: Gawrychowski, Paweł ; Manea, Florin ; Siemer, Stefan

Abstract | Document (885 KB) | BibTeX

Keyboards as a New Model of Computation

Authors: Géran, Yoan ; Laboureix, Bastien ; Mascle, Corto ; Richard, Valentin D.

Abstract | Document (817 KB) | BibTeX

Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs

Authors: Glos, Adam ; Kokainis, Martins ; Mori, Ryuhei ; Vihrovs, Jevgēnijs

Abstract | Document (902 KB) | BibTeX

A Note on the Join of Varieties of Monoids with LI

Authors: Grosshans, Nathan

Abstract | Document (767 KB) | BibTeX

Optimal Regular Expressions for Palindromes of Given Length

Authors: Gruber, Hermann ; Holzer, Markus

Abstract | Document (628 KB) | BibTeX

A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct

Authors: Guha, Shibashis ; Jecker, Ismaël ; Lehtinen, Karoliina ; Zimmermann, Martin

Abstract | Document (806 KB) | BibTeX

Perfect Forests in Graphs and Their Extensions

Authors: Gutin, Gregory ; Yeo, Anders

Abstract | Document (711 KB) | BibTeX

On Deciding Linear Arithmetic Constraints Over p-adic Integers for All Primes

Authors: Haase, Christoph ; Mansutti, Alessio

Abstract | Document (1,110 KB) | BibTeX

Obstructing Classification via Projection

Authors: Haghighatkhah, Pantea ; Meulemans, Wouter ; Speckmann, Bettina ; Urhausen, Jérôme ; Verbeek, Kevin

Abstract | Document (960 KB) | BibTeX

Online Domination: The Value of Getting to Know All Your Neighbors

Authors: Harutyunyan, Hovhannes A. ; Pankratov, Denis ; Racicot, Jesse

Abstract | Document (1,083 KB) | BibTeX

A Linear-Time Nominal μ-Calculus with Name Allocation

Authors: Hausmann, Daniel ; Milius, Stefan ; Schröder, Lutz

Abstract | Document (833 KB) | BibTeX

Test of Quantumness with Small-Depth Quantum Circuits

Authors: Hirahara, Shuichi ; Le Gall, François

Abstract | Document (712 KB) | BibTeX

On Search Complexity of Discrete Logarithm

Authors: Hubáček, Pavel ; Václavek, Jan

Abstract | Document (802 KB) | BibTeX

A Homological Condition on Equational Unifiability

Authors: Ikebuchi, Mirai

Abstract | Document (756 KB) | BibTeX

Ordered Fragments of First-Order Logic

Authors: Jaakkola, Reijo

Abstract | Document (726 KB) | BibTeX

The Simplest Non-Regular Deterministic Context-Free Language

Authors: Jančar, Petr ; Šíma, Jiří

Abstract | Document (1,014 KB) | BibTeX

On the Hardness of Compressing Weights

Authors: Jansen, Bart M. P. ; Roy, Shivesh K. ; Włodarczyk, Michał

Abstract | Document (1,288 KB) | BibTeX

Griddings of Permutations and Hardness of Pattern Matching

Authors: Jelínek, Vít ; Opler, Michal ; Pekárek, Jakub

Abstract | Document (1,154 KB) | BibTeX

Sets of Linear Forms Which Are Hard to Compute

Authors: Kaminski, Michael ; Shparlinski, Igor E.

Abstract | Document (740 KB) | BibTeX

On Positivity and Minimality for Second-Order Holonomic Sequences

Authors: Kenison, George ; Klurman, Oleksiy ; Lefaucheux, Engel ; Luca, Florian ; Moree, Pieter ; Ouaknine, Joël ; Whiteland, Markus A. ; Worrell, James

Abstract | Document (709 KB) | BibTeX

Improved Upper Bounds for the Rigidity of Kronecker Products

Authors: Kivva, Bohdan

Abstract | Document (776 KB) | BibTeX

The Power of One Clean Qubit in Communication Complexity

Authors: Klauck, Hartmut ; Lim, Debbie

Abstract | Document (1,141 KB) | BibTeX

Connecting Constructive Notions of Ordinals in Homotopy Type Theory

Authors: Kraus, Nicolai ; Nordvall Forsberg, Fredrik ; Xu, Chuangjie

Abstract | Document (803 KB) | BibTeX

Maximum Votes Pareto-Efficient Allocations via Swaps on a Social Network

Authors: Li, Fu ; Zheng, Xiong

Abstract | Document (646 KB) | BibTeX

Finite Models for a Spatial Logic with Discrete and Topological Path Operators

Authors: Linker, Sven ; Papacchini, Fabio ; Sevegnani, Michele

Abstract | Document (717 KB) | BibTeX

Recursive Backdoors for SAT

Authors: Mählmann, Nikolas ; Siebertz, Sebastian ; Vigny, Alexandre

Abstract | Document (885 KB) | BibTeX

Parallel Algorithms for Power Circuits and the Word Problem of the Baumslag Group

Authors: Mattes, Caroline ; Weiß, Armin

Abstract | Document (1,033 KB) | BibTeX

The Complexity of Transitively Orienting Temporal Graphs

Authors: Mertzios, George B. ; Molter, Hendrik ; Renken, Malte ; Spirakis, Paul G. ; Zschoche, Philipp

Abstract | Document (870 KB) | BibTeX

Temporal Reachability Minimization: Delaying vs. Deleting

Authors: Molter, Hendrik ; Renken, Malte ; Zschoche, Philipp

Abstract | Document (865 KB) | BibTeX

A Timecop’s Chase Around the Table

Authors: Morawietz, Nils ; Wolf, Petra

Abstract | Document (801 KB) | BibTeX

Syntactic Minimization Of Nondeterministic Finite Automata

Authors: Myers, Robert S. R. ; Urbat, Henning

Abstract | Document (880 KB) | BibTeX

Idempotent Turing Machines

Authors: Nakano, Keisuke

Abstract | Document (800 KB) | BibTeX

Ergodic Theorems and Converses for PSPACE Functions

Authors: Nandakumar, Satyadev ; Pulari, Subin

Abstract | Document (807 KB) | BibTeX

On Guidable Index of Tree Automata

Authors: Niwiński, Damian ; Skrzypczak, Michał

Abstract | Document (704 KB) | BibTeX

Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs

Authors: Paesani, Giacomo ; Paulusma, Daniël ; Rzążewski, Paweł

Abstract | Document (1,077 KB) | BibTeX

Stabilization Bounds for Influence Propagation from a Random Initial State

Authors: Papp, Pál András ; Wattenhofer, Roger

Abstract | Document (712 KB) | BibTeX

Parameterized (Modular) Counting and Cayley Graph Expanders

Authors: Peyerimhoff, Norbert ; Roth, Marc ; Schmitt, Johannes ; Stix, Jakob ; Vdovina, Alina

Abstract | Document (813 KB) | BibTeX

A Hierarchy of Nondeterminism

Authors: Abu Radi, Bader ; Kupferman, Orna ; Leshkowitz, Ofer

Abstract | Document (754 KB) | BibTeX

Boolean Automata and Atoms of Regular Languages

Authors: Tamm, Hellis

Abstract | Document (556 KB) | BibTeX

The Gödel Fibration

Authors: Trotta, Davide ; Spadetto, Matteo ; de Paiva, Valeria

Abstract | Document (774 KB) | BibTeX

Abstract Congruence Criteria for Weak Bisimilarity

Authors: Tsampas, Stelios ; Williams, Christian ; Nuyts, Andreas ; Devriese, Dominique ; Piessens, Frank

Abstract | Document (939 KB) | BibTeX

Quantum Multiple-Valued Decision Diagrams in Graphical Calculi

Authors: Vilmart, Renaud

Abstract | Document (759 KB) | BibTeX

Decision Problems for Origin-Close Top-Down Tree Transducers

Authors: Winter, Sarah

Abstract | Document (793 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)