45th International Symposium on

Mathematical Foundations of Computer Science

August 24-28, 2020, Prague (Czech Republic)



MFCS 2020 is organized in cooperation with EATCS


Accepted Papers

Ignasi Sau and Uéverton Souza. Hitting forbidden induced subgraphs on bounded treewidth graphs
Yasuhiro Takahashi, Yuki Takeuchi and Seiichiro Tani. Classically Simulating Quantum Circuits with Local Depolarizing Noise
Paloma de Lima, Vinicius F. dos Santos, Ignasi Sau and Uéverton S. Souza. Reducing graph transversals via edge contractions
Dietrich Kuske and Christian Schwarz. Complexity of counting first-order logic for the subword order
Jarkko Peltomäki and Markus Whiteland. All growth rates of abelian exponents are attained by infinite binary words
Zeyu Guo. Factoring polynomials over finite fields with linear Galois groups: an additive combinatorics approach
Adam Paszke and Michał Pilipczuk. VC density of set systems definable in tree-like graphs
Caterina Viola and Stanislav Živný. The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
Andreas Galanis, Leslie Ann Goldberg and James Stewart. Fast algorithms for general spin systems on bipartite expanders
Saeed Akhoondian Amiri, Alexandru Popa, Mohammad Roghani, Golnoosh Shahkarami, Reza Soltani and Hossein Vahidi. Complexity of Computing the Anti-Ramsey Numbers for Paths
Therese Biedl, Steven Chaplick, Michael Kaufmann, Fabrizio Montecchiani, Martin Nöllenburg and Chrysanthi Raftopoulou. Layered Fan-Planar Graph Drawings
Deniz Agaoglu and Petr Hlineny. Isomorphism Problem for S_d -graphs
Raul Lopes and Ignasi Sau. A relaxation of the Directed Disjoint Paths problem: a global congestion metric helps
Kim Thang Nguyen. An Improved Approximation Algorithm for Scheduling under Arborescence Precedence Constraints
Kei Uchizawa and Mitsunori Ogihara. Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR functions
Nils Morawietz, Carolin Rehs and Mathias Weller. A Timecop’s Work is Harder Than You Think
Denis Kuperberg and Jan Martens. Regular resynchronizability of origin transducers is undecidable
Louis Parlant, Jurriaan Rot, Alexandra Silva and Bas Westerbaan. Preservation of Equations by Monoidal Monads
Pavol Duris, Rastislav Královič, Richard Královič, Dana Pardubská, Martin Pašen and Peter Rossmanith. Randomization in Non-Uniform Finite Automata
Kristoffer Arnsfelt Hansen and Steffan Sølvsten. ∃R-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games
Hiroshi Hirai and Ryuhei Mizutani. Minimum 0-Extension Problems on Directed Metrics
Susanne Albers, Arindam Khan and Leon Ladewig. Best Fit Bin Packing with Random Order Revisited
Alexandre Clément and Simon Perdrix. PBS-calculus: A Graphical Language for Coherent Control of Quantum Computations
Andris Ambainis, Kaspars Balodis, Jānis Iraids, Kamil Khadiev, Vladislavs Klevitsky, Krisjanis Prusis, Yixin Shen, Juris Smotrovs and Jevgeniy Vihrov. Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
Emirhan Gürpınar and Andrei Romashchenko. Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory
Janaky Murthy, Vineet Nair and Chandan Saha. Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests
Boris Aronov, Matthew Katz and Elad Sulami. Dynamic time warping-based proximity problems
Pierre Béaur and Jarkko Kari. Decidability in Group Shifts and Group Cellular Automata
Andreas Galanis, Leslie Ann Goldberg and Andrés Herrera-Poyatos. The complexity of approximating the complex-valued Potts model
Palash Dey, Jaikumar Radhakrishnan and Santhoshini Velusamy. Improved Explicit Data Structures in the Bit-probe Model using Error Correcting Codes
Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Ismaël Jecker and Jakub Svoboda. Simplified Game of Life: Algorithms and Complexity
Alexander Rabinovich and Doron Tiferet. Ambiguity Hierarchy of Regular Infinite Tree Languages
Henning Fernau, Petra Wolf and Tomoyuki Yamakami. Synchronizing Deterministic Push-Down Automata Can Be Really Hard
Argyrios Deligkas, George Mertzios, Paul Spirakis and Viktor Zamaraev. Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
Arpitha Prasad Bharathi and Monaldo Mastrolilli. Ideal Membership Problem and a Majority Polymorphism Over the Ternary Domain
Dhawal Jethwani, Francois Le Gall and Sanjay Kumar Singh. Quantum-Inspired Classical Algorithms for Singular Value Transformation
Jungho Ahn, Eduard Eiben, O-Joung Kwon and Sang-il Oum. A polynomial kernel for 3-leaf power deletion
Vincent Michielini and Michał Skrzypczak. Regular choice functions and uniformisations for countable domains
Nathanaël Fijalkow, Pawel Gawrychowski and Pierre Ohlmann. Value iteration using universal graphs and the complexity of mean payoff games
Daniel Neider, Patrick Totzke and Martin Zimmermann. Optimally Resilient Strategies in Pushdown Safety Games
Satyadev Nandakumar and Prateek Vishnoi. Randomness and effective dimension of continued fractions
Kazuhiro Kurita and Yasuaki Kobayashi. Efficient Enumerations for Minimal Multicuts and Multiway Cuts
Stefan Jaax and Stefan Kiefer. On Affine Reachability Problems
Gaëtan Douéneau-Tabot, Emmanuel Filiot and Paul Gastin. Register transducers are marble transducers
Rian Neogi, Ramanujan M. Sridharan, Saket Saurabh and Roohani Sharma. On the Parameterized Complexity of Deletion to {\cal H}-free Strong Components
Markus Lohrey and Georg Zetzsche. Knapsack and power word problems in solvable Baumslag-Solitar groups
Max Bannach, Sebastian Berndt, Marten Maack, Matthias Mnich, Alexandra Lassota, Malin Rau and Malte Skambath. Solving Packing Problems with Few Small Items Using Rainbow Matchings
Chetan Gupta, Vimal Raj Sharma and Raghunath Tewari. Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
Sven Linker, Fabio Papacchini and Michele Sevegnani. Analysing Spatial Properties on Neighbourhood Spaces
Paloma de Lima, Erik Jan van Leeuwen and Marieke van der Wegen. Algorithms for the rainbow vertex coloring problem on graph classes
Lars Jaffke, Paloma de Lima and Geevarghese Philip. Structural Parameterizations of Clique Coloring
Orna Kupferman and Ofer Leshkowitz. On Repetition Languages
Mikołaj Bojańczyk and Janusz Schmude. Some remarks on deciding equivalence for graph-to-graph transducers
Georg Gottlob, Matthias Lanzinger, Reinhard Pichler and Igor Razgon. Fractional Covers of Hypergraphs with Bounded Multi-Intersection
Martin Böhm, Ruben Hoeksma, Nicole Megow, Lukas Nölke and Bertrand Simon. Computing a Minimum-Cost $k$-hop Steiner Tree in Tree-Like Metrics
Fedor V. Fomin, Danil Sagunov and Kirill Simonov. Building large k-cores from sparse graphs
Vittorio Bilò, Davide Bilò, Pascal Lenzner and Louise Molitor. Topological Influence and Locality in Swap Schelling Games
Laura Bozzelli, Angelo Montanari, Adriano Peron and Pietro Sala. On a temporal logic of prefixes and infixes
Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin and Chunhao Wang. Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming
Yury Elkin and Vitaliy Kurlin. The mergegram of a dendrogram and its stability
Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute and Martin Nöllenburg. Extending Nearly Complete 1-Planar Drawings in Polynomial Time
Pranabendu Misra, Fahad Panolan, Ashutosh Rai, Saket Saurabh and Roohani Sharma. Quick Separation in Chordal and Split Graphs
Jan Bok, Richard Brewster, Tomás Feder, Pavol Hell and Nikola Jedličková. List homomorphism problems for signed graphs
Junhao Gan, David Gleich, Nate Veldt, Anthony Wirth and Xin Zhang. Graph Clustering in All Parameter Regimes
Markus Bläser and Vladimir Lysikov. Slice rank of block tensors and irreversibility of structure tensors of algebras
Arindam Biswas, Venkatesh Raman and Saket Saurabh. Approximation in (Poly)logarithmic Space
Jan Kratochvíl, Tomáš Masařík and Jana Novotná. U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
Pierre Ganty, Elena Gutiérrez and Pedro Valero. A Quasiorder-based Perspective on Residual Automata
Ismaël Jecker, Orna Kupferman and Nicolas Mazzocchi. Unary Prime Languages
Sophie Laplante, Reza Naserasr and Anupa Sunny. Sensitivity lower bounds from linear dependencies
Alexandre Vigny, Sebastian Siebertz and Alexander Lindermayr. Elimination Distance to Bounded Degree on Planar Graphs
Svein Høgemo, Christophe Paul and Jan Arne Telle. Hierarchical Clusterings of Unweighted Graphs
Mikhail Rubinchik and Arseny Shur. Palindromic k-Factorization in Pure Linear Time
Arjan Cornelissen, Stacey Jeffery, Maris Ozols and Alvaro Piedrafita. Span programs and quantum time complexity
Paul Gallot, Sylvain Salvati and Aurélien Lemay. Linear High-Order Deterministic Tree transducers with Regular look-ahead
Michal Konecny, Florian Steinberg and Holger Thies. Continuous and monotone machines
Piotr Kawałek and Jacek Krzaczkowski. Even faster algorithms for CSAT over supernilpotent algebras
Alessio Conte, Pierluigi Crescenzi, Andrea Marino and Giulia Punzi. Enumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal Graphs
Toghrul Karimov, Joel Ouaknine and James Worrell. On LTL Model Checking for Low-Dimensional Discrete Linear Dynamical Systems
Vikraman Arvind, Abhranil Chatterjee, Rajit Datta and Partha Mukhopadhyay. A Special Case of Rational Identity Testing and the Bre\v{s}ar-Klep Theorem
Lars Jaffke, Mateus De Oliveira Oliveira and Hans Raj Tiwary. Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach
Vít Jelínek, Michal Opler and Jakub Pekárek. A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes

Important Dates

Paper submission deadline:    Monday, May 4, 2020 (AoE)   
Notification of authors: Monday, June 29, 2020   
Conference dates: August 24–28, 2020
Workshop dates: August 28–29, 2020

Contact: Andreas Emil Feldmann feldmann.a.e@gmail.com