45th International Symposium on

Mathematical Foundations of Computer Science

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



MFCS 2020 is organized in cooperation with EATCS



All times are quoted in UTC+2 (Prague time).
13:00-13:50 Invited talk - Sergio Cabello (Ljubljana) 13:00-13:50 Invited talk - Nathalie Bertrand (INRIA, Rennes)
14:00-15:00 Q/A Sessions 1 14:00-15:00 Q/A Sessions 3
15:00-15:30 Gather.town break 15:00-15:30 Gather.town break
15:30-16:20 Invited talk - Parthasarathy Madhusudan (UIUC) 15:30-16:20 Invited talk - Subhash Khot (NYU)
16:30-17:30 Q/A Sessions 2 16:30-17:20 Q/A Sessions 4
17:30-18:00 Gather.town break 17:20-17:50 Gather.town break
18:00-18:50 Invited talk - Mary Wootters (Stanford) 17:50-18:40 Q/A Sessions 5
19:00-20:00 Gather.town social 18:40-19:00 Gather.town break


All sessions except for Gather.town will be available via Zoom. Gather.town sessions will be available through web browsers and do not need any special software installed. Registered participants will receive access information via email.

Q/A Sessions will run as three parallel sessions. Each paper has assigned 10 minute slot, where we expect the authors to have a 5-7 minute presentation and the rest of the time will be available for questions. We ask all presenting authors to join their sessions via Zoom at least 10-15 minutes before the actual start of the session. They will run their presentation on their computer and share it via Zoom "Share screen" feature once requested by the session chair. To facilitate further questions to the authors after each session we ask the authors of each paper from a given session to attend the Gather.town break where their papers will have designated clearly marked spots/locations. Attendees interested in asking questions to the authors can locate the corresponding spot in the Gather.town and start audio/video conversation with the present authors.

Gather.town will be available continuously between 12:30 and 20:30 on each day.

Q/A Sessions 1

TUE 14:00-15:00 UTC+2
when is this in my timezone?

Q/A Session 1A

Session chair(s): TBA
14:00Pierre Béaur and Jarkko Kari Decidability in Group Shifts and Group Cellular Automata
14:10Henning Fernau, Petra Wolf and Tomoyuki Yamakami Synchronizing Deterministic Push-Down Automata Can Be Really Hard
14:20Pierre Ganty, Elena Gutiérrez and Pedro Valero A Quasiorder-based Perspective on Residual Automata
14:30Ismaël Jecker, Orna Kupferman and Nicolas Mazzocchi Unary Prime Languages
14:40Orna Kupferman and Ofer Leshkowitz On Repetition Languages
14:50Alexander Rabinovich and Doron Tiferet Ambiguity Hierarchy of Regular Infinite Tree Languages

Q/A Session 1B

Session chair(s): TBA
14:00Jungho Ahn, Eduard Eiben, O-Joung Kwon and Sang-il Oum A polynomial kernel for 3-leaf power deletion
14:10Arindam Biswas, Venkatesh Raman and Saket Saurabh Approximation in (Poly)logarithmic Space
14:20Argyrios Deligkas, George Mertzios, Paul Spirakis and Viktor Zamaraev Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
14:30Lars Jaffke, Paloma de Lima and Geevarghese Philip Structural Parameterizations of Clique Coloring
14:40Paloma de Lima, Erik Jan van Leeuwen and Marieke van der Wegen Algorithms for the rainbow vertex coloring problem on graph classes
14:50Ignasi Sau and Uéverton Souza Hitting forbidden induced subgraphs on bounded treewidth graphs

Q/A Session 1C

Session chair(s): TBA
14:00Vikraman Arvind, Abhranil Chatterjee, Rajit Datta and Partha Mukhopadhyay A Special Case of Rational Identity Testing and the Bre\v{s}ar-Klep Theorem
14:10Markus Bläser and Vladimir Lysikov Slice rank of block tensors and irreversibility of structure tensors of algebras
14:20Palash Dey, Jaikumar Radhakrishnan and Santhoshini Velusamy Improved Explicit Data Structures in the Bit-probe Model using Error Correcting Codes
14:30Andreas Galanis, Leslie Ann Goldberg and Andrés Herrera-Poyatos The complexity of approximating the complex-valued Potts model
14:40Zeyu Guo Factoring polynomials over finite fields with linear Galois groups: an additive combinatorics approach
14:50Satyadev Nandakumar and Prateek Vishnoi Randomness and effective dimension of continued fractions

Q/A Sessions 2

TUE 16:30-17:30 UTC+2
when is this in my timezone?

Q/A Session 2A

Session chair(s): TBA
16:30Andris Ambainis, Kaspars Balodis, Janis 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
16:40Dietrich Kuske and Christian Schwarz Complexity of counting first-order logic for the subword order
16:50Vincent Michielini and Michal Skrzypczak Regular choice functions and uniformisations for countable domains
17:00Adam Paszke and Michal Pilipczuk VC density of set systems definable in tree-like graphs
17:10Jarkko Peltomäki and Markus Whiteland All growth rates of abelian exponents are attained by infinite binary words
17:20Mikhail Rubinchik and Arseny Shur Palindromic k-Factorization in Pure Linear Time

Q/A Session 2B

Session chair(s): TBA
16:30Yury Elkin and Vitaliy Kurlin The mergegram of a dendrogram and its stability
16:40Junhao Gan, David Gleich, Nate Veldt, Anthony Wirth and Xin Zhang Graph Clustering in All Parameter Regimes
16:50Georg Gottlob, Matthias Lanzinger, Reinhard Pichler and Igor Razgon Fractional Covers of Hypergraphs with Bounded Multi-Intersection
17:00Svein Høgemo, Christophe Paul and Jan Arne Telle Hierarchical Clusterings of Unweighted Graphs
17:10Vít Jelínek, Michal Opler and Jakub Pekárek A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes
17:20Sophie Laplante, Reza Naserasr and Anupa Sunny Sensitivity lower bounds from linear dependencies

Q/A Session 2C

Session chair(s): TBA
16:30Susanne Albers, Arindam Khan and Leon Ladewig Best-Fit Bin Packing with Random Order Revisited (Best paper award)
16:40Max Bannach, Sebastian Berndt, Marten Maack, Matthias Mnich, Alexandra Lassota, Malin Rau and Malte Skambath Solving Packing Problems with Few Small Items Using Rainbow Matchings
16:50Vittorio Bilò, Davide Bilò, Pascal Lenzner and Louise Molitor Topological Influence and Locality in Swap Schelling Games
17:00Andreas Galanis, Leslie Ann Goldberg and James Stewart Fast algorithms for general spin systems on bipartite expanders
17:10Emirhan Gürpınar and Andrei Romashchenko Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory
17:20Kim Thang Nguyen An Improved Approximation Algorithm for Scheduling under Arborescence Precedence Constraints

Q/A Sessions 3

WED 14:00-15:00 UTC+2
when is this in my timezone?

Q/A Session 3A

Session chair(s): TBA
14:00Mikołaj Bojańczyk and Janusz Schmude Some remarks on deciding equivalence for graph-to-graph transducers (Best paper award)
14:10Gaëtan Douéneau-Tabot, Emmanuel Filiot and Paul Gastin Register transducers are marble transducers
14:20Paul Gallot, Sylvain Salvati and Aurélien Lemay Linear High-Order Deterministic Tree transducers with Regular look-ahead
14:30Lars Jaffke, Mateus De Oliveira Oliveira and Hans Raj Tiwary Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach
14:40Denis Kuperberg and Jan Martens Regular resynchronizability of origin transducers is undecidable
14:50Markus Lohrey and Georg Zetzsche Knapsack and power word problems in solvable Baumslag-Solitar groups

Q/A Session 3B

Session chair(s): TBA
14:00Saeed Akhoondian Amiri, Alexandru Popa, Mohammad Roghani, Golnoosh Shahkarami, Reza Soltani and Hossein Vahidi Complexity of Computing the Anti-Ramsey Numbers for Paths
14:10Jan Bok, Richard Brewster, Tomás Feder, Pavol Hell and Nikola Jedličková List homomorphism problems for signed graphs
14:20Fedor V. Fomin, Danil Sagunov and Kirill Simonov Building large k-cores from sparse graphs
14:30Paloma de Lima, Vinicius F. dos Santos, Ignasi Sau and Uéverton S. Souza Reducing graph transversals via edge contractions
14:40Rian Neogi, Ramanujan M. Sridharan, Saket Saurabh and Roohani Sharma On the Parameterized Complexity of Deletion to H-free Strong Components
14:50Alexandre Vigny, Sebastian Siebertz and Alexander Lindermayr Elimination Distance to Bounded Degree on Planar Graphs

Q/A Session 3C

Session chair(s): TBA
14:00Alessio Conte, Pierluigi Crescenzi, Andrea Marino and Giulia Punzi Enumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal Graphs
14:10Chetan Gupta, Vimal Raj Sharma and Raghunath Tewari Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
14:20Jan Kratochvíl, Tomáš Masařík and Jana Novotná U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
14:30Kazuhiro Kurita and Yasuaki Kobayashi Efficient Enumerations for Minimal Multicuts and Multiway Cuts
14:40Raul Lopes and Ignasi Sau A relaxation of the Directed Disjoint Paths problem: a global congestion metric helps
14:50Pranabendu Misra, Fahad Panolan, Ashutosh Rai, Saket Saurabh and Roohani Sharma Quick Separation in Chordal and Split Graphs

Q/A Sessions 4

WED 16:30-17:20 UTC+2
when is this in my timezone?

Q/A Session 4A

Session chair(s): TBA
16:30Kristoffer Arnsfelt Hansen and Steffan Sølvsten ∃R-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games
16:40Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Ismaël Jecker and Jakub Svoboda Simplified Game of Life: Algorithms and Complexity
16:50Nathanaël Fijalkow, Pawel Gawrychowski and Pierre Ohlmann Value iteration using universal graphs and the complexity of mean payoff games
17:00Nils Morawietz, Carolin Rehs and Mathias Weller A Timecop’s Work is Harder Than You Think
17:10Daniel Neider, Patrick Totzke and Martin Zimmermann Optimally Resilient Strategies in Pushdown Safety Games

Q/A Session 4B

Session chair(s): TBA
16:30Deniz Agaoglu and Petr Hlineny Isomorphism Problem for S_d -graphs
16:40Boris Aronov, Matthew Katz and Elad Sulami Dynamic time warping-based proximity problems
16:50Therese Biedl, Steven Chaplick, Michael Kaufmann, Fabrizio Montecchiani, Martin Nöllenburg and Chrysanthi Raftopoulou Layered Fan-Planar Graph Drawings
17:00Martin Böhm, Ruben Hoeksma, Nicole Megow, Lukas Nölke and Bertrand Simon Computing a Minimum-Cost $k$-hop Steiner Tree in Tree-Like Metrics
17:10Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute and Martin Nöllenburg Extending Nearly Complete 1-Planar Drawings in Polynomial Time

Q/A Session 4C

Session chair(s): TBA
16:30Alexandre Clément and Simon Perdrix PBS-calculus: A Graphical Language for Coherent Control of Quantum Computations
16:40Pavol Duris, Rastislav Královič, Richard Královič, Dana Pardubská, Martin Pašen and Peter Rossmanith Randomization in Non-Uniform Finite Automata
16:50Michal Konecny, Florian Steinberg and Holger Thies Continuous and monotone machines
17:00Sven Linker, Fabio Papacchini and Michele Sevegnani Analysing Spatial Properties on Neighbourhood Spaces
17:10Louis Parlant, Jurriaan Rot, Alexandra Silva and Bas Westerbaan Preservation of Equations by Monoidal Monads

Q/A Sessions 5

WED 17:50-18:40 UTC+2
when is this in my timezone?

Q/A Session 5A

Session chair(s): TBA
17:50Laura Bozzelli, Angelo Montanari, Adriano Peron and Pietro Sala On a temporal logic of prefixes and infixes
18:00Stefan Jaax and Stefan Kiefer On Affine Reachability Problems
18:10Toghrul Karimov, Joel Ouaknine and James Worrell On LTL Model Checking for Low-Dimensional Discrete Linear Dynamical Systems
18:20Janaky Murthy, Vineet Nair and Chandan Saha Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests
18:30Kei Uchizawa and Mitsunori Ogihara Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR functions

Q/A Session 5B

Session chair(s): TBA
17:50Hiroshi Hirai and Ryuhei Mizutani Minimum 0-Extension Problems on Directed Metrics
18:00Piotr Kawałek and Jacek Krzaczkowski Even faster algorithms for CSAT over supernilpotent algebras
18:10Arpitha Prasad Bharathi and Monaldo Mastrolilli Ideal Membership Problem and a Majority Polymorphism Over the Ternary Domain
18:20Caterina Viola and Stanislav Živný The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains

Q/A Session 5C

Session chair(s): TBA
17:50Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin and Chunhao Wang Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming
18:00Arjan Cornelissen, Stacey Jeffery, Maris Ozols and Alvaro Piedrafita Span programs and quantum time complexity
18:10Dhawal Jethwani, Francois Le Gall and Sanjay Kumar Singh Quantum-Inspired Classical Algorithms for Singular Value Transformation
18:20Yasuhiro Takahashi, Yuki Takeuchi and Seiichiro Tani Classically Simulating Quantum Circuits with Local Depolarizing Noise

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