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).
TimeTuesday, August 25TimeWednesday, August 26
13:00-13:50 Invited talk - Sergio Cabello (Ljubljana) 13:00-13:50 Invited talk - Subhash Khot (NYU)
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 - Nathalie Bertrand (INRIA, Rennes)
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 on Friday, August 21.

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.

We suggest to all presenting authors to use a good internet connection (preferably wired) and use a local installation of Zoom (which is free to install.).

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

Invited talks

Sergio Cabello (Ljubljana)

Session chair(s): Dan Kral

TUE 13:00-13:50 UTC+2
when is this in my timezone?

Some Open Problems in Computational Geometry

We shall encounter three open problems in Computational Geometry that are, in my opinion, interesting for a general audience interested in algorithms.

Parthasarathy Madhusudan (UIUC)

Session chair(s): Naoki Kobayashi

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

First-Order Logics with Recursive Definitions for Program Verification

We argue that first order logic with recursive definitions augmented with background theories forms an interesting, expressive, and largely automatable logic for formal verification of programs that manipulate datastructures. We will survey several recent results: (a) a heuristic technique called natural proofs that works well in practice and, theoretically, gives complete reasoning for certain FO logics with background theories, (b) a first order logic extended with frames that provides frame reasoning to ease proofs, and (c) techniques for tackling recursive definitions, which call for reasoning with least fixpoints, by divining hypotheses for inductive proofs using program/expression synthesis. These techniques are mainly evaluated in verification frameworks for programs that manipulate datastructures.

Mary Wootters (Stanford)

Session chair(s): Standa Živný

TUE 18:00-18:50 UTC+2
when is this in my timezone?

List-Decodability of Structured Ensembles of Codes

What combinatorial properties are satisfied by a random subspace over a finite field? For example, is it likely that not too many points lie in any Hamming ball? What about any cube? In this talk, I will discuss the answer to these questions, along with a more general characterization of the properties that are likely to be satisfied by a random subspace. The motivation for this characterization comes from error correcting codes. I will discuss how to use this characterization to make progress on the questions of list-decoding and list-recovery for random linear codes, and also to establish the list-decodability of random Low Density Parity-Check (LDPC) codes.

This talk is based on the joint works with Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, and Shashwat Silas.

Subhash Khot (NYU)

Session chair(s): László Végh

WED 13:00-13:50 UTC+2
when is this in my timezone?

Hardness of Approximation: From the PCP Theorem to the 2-to-2 Games Theorems

Computer scientists firmly believe that no algorithm can efficiently compute optimal solutions to a class of problems called NP-hard problems. For many NP-hard problems, even computing an approximately optimal solution remains NP-hard. This phenomenon, known as the hardness of approximation, has numerous connections to proof checking, optimization, combinatorics , discrete Fourier analysis, and geometry.

The talk will provide an overview of these connections. It will address why graph coloring is a computationally hard problem, how it is possible to check a proof without even looking at it, why computer scientists love the majority vote, and whether a shape exists that looks spherical as well as cubical. It will explain how all this fits into a 30-year research program starting with the foundational Probabilistically Checkable Proofs (PCP) Theorem and leading to the recent 2-to-2 Games Theorem.

Nathalie Bertrand (INRIA, Rennes)

Session chair(s): Javier Esparza

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

Concurrent Games with Arbitrarily Many Playerss

Traditional concurrent games on graphs involve a fixed number of players, who take decisions simultaneously, determining the next state of the game. With Anirban Majumdar and Patricia Bouyer, we introduced a parameterized variant of concurrent games on graphs, where the parameter is precisely the number of players. Parameterized concurrent games are described by finite graphs, in which the transitions bear finite-word languages to describe the possible move combinations that lead from one vertex to another.

We report on results on two problems for such concurrent games with arbitrary many players.

To start with, we studied the problem of determining whether the first player, say Eve, has a strategy to ensure a reachability objective against any strategy profile of her opponents as a coalition. In particular Eve's strategy should be independent of the number of opponents she actually has. We establish the precise complexities of the problem for reachability objectives.

Second, we considered a synthesis problem, where one aims at designing a strategy for each of the (arbitrarily many) players so as to achieve a common objective. For safety objectives, we show that this kind of distributed synthesis problem is decidable.

Q/A Sessions 1

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

Q/A Session 1A

Session chair(s): Artur Jez
TimeAuthorsTitle DOIYouTube
14:00Pierre Béaur and Jarkko KariDecidability in Group Shifts and Group Cellular AutomataDOI video
14:10Henning Fernau, Petra Wolf and Tomoyuki YamakamiSynchronizing Deterministic Push-Down Automata Can Be Really HardDOI video
14:20Pierre Ganty, Elena Gutiérrez and Pedro ValeroA Quasiorder-based Perspective on Residual AutomataDOI video
14:30Ismaël Jecker, Orna Kupferman and Nicolas MazzocchiUnary Prime LanguagesDOI video
14:40Orna Kupferman and Ofer LeshkowitzOn Repetition LanguagesDOI video
14:50Alexander Rabinovich and Doron TiferetAmbiguity Hierarchy of Regular Infinite Tree LanguagesDOI video

Q/A Session 1B

Session chair(s): Jakub Gajarský
TimeAuthorsTitle DOIYouTube
14:00Jungho Ahn, Eduard Eiben, O-Joung Kwon and Sang-il OumA polynomial kernel for 3-leaf power deletionDOI video
14:10Arindam Biswas, Venkatesh Raman and Saket SaurabhApproximation in (Poly)logarithmic SpaceDOI video
14:20Argyrios Deligkas, George Mertzios, Paul Spirakis and Viktor ZamaraevExact and Approximate Algorithms for Computing a Second Hamiltonian CycleDOI video
14:30Lars Jaffke, Paloma de Lima and Geevarghese PhilipStructural Parameterizations of Clique ColoringDOI video
14:40Paloma de Lima, Erik Jan van Leeuwen and Marieke van der WegenAlgorithms for the rainbow vertex coloring problem on graph classesDOI video
14:50Ignasi Sau and Uéverton SouzaHitting forbidden induced subgraphs on bounded treewidth graphsDOI video

Q/A Session 1C

Session chair(s): Iddo Tzameret
TimeAuthorsTitle DOIYouTube
14:00Vikraman Arvind, Abhranil Chatterjee, Rajit Datta and Partha MukhopadhyayA Special Case of Rational Identity Testing and the Bre\v{s}ar-Klep TheoremDOI video
14:10Markus Bläser and Vladimir LysikovSlice rank of block tensors and irreversibility of structure tensors of algebrasDOI video
14:20Palash Dey, Jaikumar Radhakrishnan and Santhoshini VelusamyImproved Explicit Data Structures in the Bit-probe Model using Error Correcting CodesDOI video
14:30Andreas Galanis, Leslie Ann Goldberg and Andrés Herrera-PoyatosThe complexity of approximating the complex-valued Potts modelDOI video
14:40Zeyu GuoFactoring polynomials over finite fields with linear Galois groups: an additive combinatorics approachDOI video
14:50Satyadev Nandakumar and Prateek VishnoiRandomness and effective dimension of continued fractionsDOI video

Q/A Sessions 2

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

Q/A Session 2A

Session chair(s): Dirk Nowotka
TimeAuthorsTitle DOIYouTube
16:30Andris Ambainis, Kaspars Balodis, Janis Iraids, Kamil Khadiev, Vladislavs Klevitsky, Krisjanis Prusis, Yixin Shen, Juris Smotrovs and Jevgeniy VihrovQuantum Lower and Upper Bounds for 2D-Grid and Dyck LanguageDOI video
16:40Dietrich Kuske and Christian SchwarzComplexity of counting first-order logic for the subword orderDOI video
16:50Vincent Michielini and Michal SkrzypczakRegular choice functions and uniformisations for countable domainsDOI video
17:00Adam Paszke and Michal PilipczukVC density of set systems definable in tree-like graphsDOI video
17:10Jarkko Peltomäki and Markus WhitelandAll growth rates of abelian exponents are attained by infinite binary wordsDOI video
17:20Mikhail Rubinchik and Arseny ShurPalindromic k-Factorization in Pure Linear TimeDOI video

Q/A Session 2B

Session chair(s): Lukasz Kowalik
TimeAuthorsTitle DOIYouTube
16:30Yury Elkin and Vitaliy KurlinThe mergegram of a dendrogram and its stabilityDOI video
16:40Junhao Gan, David Gleich, Nate Veldt, Anthony Wirth and Xin ZhangGraph Clustering in All Parameter RegimesDOI video
16:50Georg Gottlob, Matthias Lanzinger, Reinhard Pichler and Igor RazgonFractional Covers of Hypergraphs with Bounded Multi-IntersectionDOI video
17:00Svein Høgemo, Christophe Paul and Jan Arne TelleHierarchical Clusterings of Unweighted GraphsDOI video
17:10Vít Jelínek, Michal Opler and Jakub PekárekA Complexity Dichotomy for Permutation Pattern Matching on Grid ClassesDOI video
17:20Sophie Laplante, Reza Naserasr and Anupa SunnySensitivity lower bounds from linear dependenciesDOI video

Q/A Session 2C

Session chair(s): Matthias Englert
TimeAuthorsTitle DOIYouTube
16:30Susanne Albers, Arindam Khan and Leon LadewigBest Fit Bin Packing with Random Order Revisited (Best paper award)DOI video
16:40Max Bannach, Sebastian Berndt, Marten Maack, Matthias Mnich, Alexandra Lassota, Malin Rau and Malte SkambathSolving Packing Problems with Few Small Items Using Rainbow MatchingsDOI video
16:50Vittorio Bilò, Davide Bilò, Pascal Lenzner and Louise MolitorTopological Influence and Locality in Swap Schelling GamesDOI video
17:00Andreas Galanis, Leslie Ann Goldberg and James StewartFast algorithms for general spin systems on bipartite expandersDOI video
17:10Emirhan Gürpınar and Andrei RomashchenkoCommunication Complexity of the Secret Key Agreement in Algorithmic Information TheoryDOI video
17:20Kim Thang NguyenAn Improved Approximation Algorithm for Scheduling under Arborescence Precedence ConstraintsDOI N/A

Q/A Sessions 3

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

Q/A Session 3A

Session chair(s): Thomas Colcombet
TimeAuthorsTitle DOIYouTube
14:00Mikołaj Bojańczyk and Janusz SchmudeSome remarks on deciding equivalence for graph-to-graph transducers (Best paper award)DOI video
14:10Gaëtan Douéneau-Tabot, Emmanuel Filiot and Paul GastinRegister transducers are marble transducersDOI video
14:20Paul Gallot, Sylvain Salvati and Aurélien LemayLinear High-Order Deterministic Tree transducers with Regular look-aheadDOI video
14:30Lars Jaffke, Mateus De Oliveira Oliveira and Hans Raj TiwaryCompressing Permutation Groups into Grammars and Polytopes. A Graph Embedding ApproachDOI video
14:40Denis Kuperberg and Jan MartensRegular resynchronizability of origin transducers is undecidableDOI video
14:50Markus Lohrey and Georg ZetzscheKnapsack and power word problems in solvable Baumslag-Solitar groupsDOI video

Q/A Session 3B

Session chair(s): Standa Živný
TimeAuthorsTitle DOIYouTube
14:00Saeed Akhoondian Amiri, Alexandru Popa, Mohammad Roghani, Golnoosh Shahkarami, Reza Soltani and Hossein VahidiComplexity of Computing the Anti-Ramsey Numbers for PathsDOI video
14:10Jan Bok, Richard Brewster, Tomás Feder, Pavol Hell and Nikola JedličkováList homomorphism problems for signed graphsDOI video
14:20Fedor V. Fomin, Danil Sagunov and Kirill SimonovBuilding large k-cores from sparse graphsDOI video
14:30Paloma de Lima, Vinicius F. dos Santos, Ignasi Sau and Uéverton S. SouzaReducing graph transversals via edge contractionsDOI video
14:40Rian Neogi, Ramanujan M. Sridharan, Saket Saurabh and Roohani SharmaOn the Parameterized Complexity of Deletion to H-free Strong ComponentsDOI video
14:50Alexandre Vigny, Sebastian Siebertz and Alexander LindermayrElimination Distance to Bounded Degree on Planar GraphsDOI video

Q/A Session 3C

Session chair(s): László Végh
TimeAuthorsTitle DOIYouTube
14:00Martin Böhm, Ruben Hoeksma, Nicole Megow, Lukas Nölke and Bertrand SimonComputing a Minimum-Cost $k$-hop Steiner Tree in Tree-Like MetricsDOI video
14:10Alessio Conte, Pierluigi Crescenzi, Andrea Marino and Giulia PunziEnumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal GraphsDOI video
14:20Chetan Gupta, Vimal Raj Sharma and Raghunath TewariEfficient Isolation of Perfect Matching in O(log n) Genus Bipartite GraphsDOI video
14:30Kazuhiro Kurita and Yasuaki KobayashiEfficient Enumerations for Minimal Multicuts and Multiway CutsDOI video
14:40Raul Lopes and Ignasi SauA relaxation of the Directed Disjoint Paths problem: a global congestion metric helpsDOI video
14:50Pranabendu Misra, Fahad Panolan, Ashutosh Rai, Saket Saurabh and Roohani SharmaQuick Separation in Chordal and Split GraphsDOI video

Q/A Sessions 4

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

Q/A Session 4A

Session chair(s): Mickael Randour
TimeAuthorsTitle DOIYouTube
16:30Kristoffer Arnsfelt Hansen and Steffan Sølvsten∃R-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic GamesDOI video
16:40Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Ismaël Jecker and Jakub SvobodaSimplified Game of Life: Algorithms and ComplexityDOI video
16:50Nathanaël Fijalkow, Pawel Gawrychowski and Pierre OhlmannValue iteration using universal graphs and the complexity of mean payoff gamesDOI video
17:00Nils Morawietz, Carolin Rehs and Mathias WellerA Timecop’s Work is Harder Than You Think DOI video
17:10Daniel Neider, Patrick Totzke and Martin ZimmermannOptimally Resilient Strategies in Pushdown Safety GamesDOI video

Q/A Session 4B

Session chair(s): Broňa Brejová
TimeAuthorsTitle DOIYouTube
16:30Deniz Agaoglu and Petr HlinenyIsomorphism Problem for S_d -graphsDOI video
16:40Boris Aronov, Matthew Katz and Elad SulamiDynamic time warping-based proximity problemsDOI video
16:50Therese Biedl, Steven Chaplick, Michael Kaufmann, Fabrizio Montecchiani, Martin Nöllenburg and Chrysanthi RaftopoulouLayered Fan-Planar Graph DrawingsDOI video
17:00Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute and Martin NöllenburgExtending Nearly Complete 1-Planar Drawings in Polynomial TimeDOI video
17:10Jan Kratochvíl, Tomáš Masařík and Jana NovotnáU-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem RevisitedDOI video

Q/A Session 4C

Session chair(s): Matthew Hague
TimeAuthorsTitle DOIYouTube
16:30Alexandre Clément and Simon PerdrixPBS-calculus: A Graphical Language for Coherent Control of Quantum ComputationsDOI video
16:40Pavol Duris, Rastislav Královič, Richard Královič, Dana Pardubská, Martin Pašen and Peter RossmanithRandomization in Non-Uniform Finite AutomataDOI video
16:50Michal Konecny, Florian Steinberg and Holger ThiesContinuous and monotone machinesDOI video
17:00Sven Linker, Fabio Papacchini and Michele SevegnaniAnalysing Spatial Properties on Neighbourhood SpacesDOI video
17:10Louis Parlant, Jurriaan Rot, Alexandra Silva and Bas WesterbaanPreservation of Equations by Monoidal MonadsDOI video

Q/A Sessions 5

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

Q/A Session 5A

Session chair(s): Michael Blondin
TimeAuthorsTitle DOIYouTube
17:50Laura Bozzelli, Angelo Montanari, Adriano Peron and Pietro SalaOn a temporal logic of prefixes and infixesDOI video
18:00Stefan Jaax and Stefan KieferOn Affine Reachability ProblemsDOI video
18:10Toghrul Karimov, Joel Ouaknine and James WorrellOn LTL Model Checking for Low-Dimensional Discrete Linear Dynamical SystemsDOI video
18:20Janaky Murthy, Vineet Nair and Chandan SahaRandomized polynomial-time equivalence between determinant and trace-IMM equivalence testsDOI video
18:30Kei Uchizawa and Mitsunori OgiharaSynchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR functionsDOI video

Q/A Session 5B

Session chair(s): Lukasz Kowalik
TimeAuthorsTitle DOIYouTube
17:50Hiroshi Hirai and Ryuhei MizutaniMinimum 0-Extension Problems on Directed MetricsDOI video
18:00Piotr Kawałek and Jacek KrzaczkowskiEven faster algorithms for CSAT over supernilpotent algebrasDOI video
18:10Arpitha Prasad Bharathi and Monaldo MastrolilliIdeal Membership Problem and a Majority Polymorphism Over the Ternary DomainDOI video
18:20Caterina Viola and Stanislav ŽivnýThe combined basic LP and affine IP relaxation for promise VCSPs on infinite domainsDOI video

Q/A Session 5C

Session chair(s): Iddo Tzameret
TimeAuthorsTitle DOIYouTube
17:50Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin and Chunhao WangQuantum-inspired sublinear algorithm for solving low-rank semidefinite programmingDOI video
18:00Arjan Cornelissen, Stacey Jeffery, Maris Ozols and Alvaro PiedrafitaSpan programs and quantum time complexityDOI video
18:10Dhawal Jethwani, Francois Le Gall and Sanjay Kumar SinghQuantum-Inspired Classical Algorithms for Singular Value TransformationDOI video
18:20Yasuhiro Takahashi, Yuki Takeuchi and Seiichiro TaniClassically Simulating Quantum Circuits with Local Depolarizing NoiseDOI video

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