44th International Symposium on

Mathematical Foundations of Computer Science

August 26-30, 2019, Aachen (Germany)

MFCS 2019 is organized in cooperation with EATCS


Conference Program

Program Overview

Monday Tuesday Wednesday Thursday Friday
time (August 26th) (August 27th) (August 28th) (August 29th) (August 30th)
08:20-08:50 Registration Registration & Refreshments
09:00-10:00 Invited Talk:
Invited Talk:
Invited Talk:
Invited Talk:
Invited Talk:
10:00-10:40 Coffee Break
10:40-12:00 Session 1A/1B Session 4A/4B Session 7A/7B Session 9A/9B Session 12A/12B
12:00-14:00 Lunch
14:00-15:40 Session 2A/2B Session 5A/5B Session 8A/8B Session 10A/10B Workshops:
ARDA 2019
Fri. 14:00 - 19:00
Structural Sparseness
Fri. 14:00 - 19:00
Sat. 9:00 - 16:00
15:40-16:10 Coffee Break
16:10-17:30 Session 3A/3B Session 6A/6B Session 11A/11B


Monday, August 26th
08:20 - 08:50
Registration & Refreshments
08:50 - 09:00
09:00 - 10:00
Invited Talk:
Kurt Mehlhorn
Trustworthy Graph Algorithms
10:00 - 10:40
Coffee Break
10:40 - 12:00 1A - Online Algorithms 1B - Games
M. Bieńkowski, H. Liu
An Improved Online Algorithm for Traveling Repairperson Problem on a Line
P. Bouyer, N. Thomasset
Nash equilibria in games over graphs equipped with a communication mechanism
M. de Lima, M. Halldórsson
Query-Competitive Sorting with Uncertainty
P. Parys
Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
M. Bieńkowski, J. Byrka, M. Chrobak, C. Coester, Ł. Jeż, E. Koutsoupias
Better Bounds for Online Line Chasing
G. Avni, T. Henzinger, D. Žikelić
Bidding Mechanisms in Graph Games
12:00 - 14:00
14:00 - 15:40 2A - Graph Algorithms 2B - First-Order Logic
A. Konstantinidis, C. Papadopoulos
Cluster Deletion on Interval Graphs and Split Related Graphs
E. Kieroński
One-dimensional guarded fragments
H. Le, V. Bang Le
Constrained representations of map graphs and half-squares
D. Danielski, E. Kieroński
Finite Satisfiability of Unary Negation Fragment with Transitivity
B. Martin, D. Paulusma, S. Smith
Colouring H-free Graphs of Bounded Diameter
L. Tendera, I. Pratt-Hartmann
Fluted Fragment with Transitivity
V. Chepoi, A. Labourel, S. Ratel
Distance labeling schemes for cube-free median graphs
A. Haak, J. Kontinen, F. Müller, H. Vollmer, F. Yang
Counting of Teams in First-Order Team Logics
15:40 - 16:10
Coffee Break
16:10 - 17:30 3A - Approximation Algorithms 3B - Algebraic and Differential Equations
Z. Nutov, G. Kortsarz, E. Shalom
Approximating activation edge-cover and facility location problems
O. Bournez, A. Durand
Recursion schemes, discrete differential equations and characterization of polynomial time computation
C. Konrad, V. Zamaraev
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
M. Boreale
On the coalgebra of partial differential equations
E. Bampis, B. Escoffier, A. Teiller
Multistage Knapsack
Z. Gao, S. Jain, B. Khoussainov, W. Li, A. Melnikov, K. Seidel, F. Stephan
Random subgroups of rationals

Tuesday, August 27th
08:20 - 09:00
Registration & Refreshments
09:00 - 10:00
Invited Talk:
Alexandra Silva
Guarded Kleene Algebra with Tests:
Verification of Uninterpreted Programs in Nearly Linear Time
10:00 - 10:40
Coffee Break
10:40 - 12:00 4A - Parameterized Algorithms I 4B - Logic I
J. Dörfler, M. Roth, J. Schmitt, P. Wellnitz
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness
D. Figueira, V. Ramanathan, P. Weil
The Quantifier Alternation Hierarchy of Synchronous Relations
S. Bessy, M. Bougeret, R. Krithika, A. Sahu, S. Saurabh, J. Thiebaut, M. Zehavi
Packing Arc-Disjoint Cycles in Tournaments
A. Padmanabha, R. Ramanujam
Two variable fragment of Term Modal Logic
J. Madathil, R. Sharma, M. Zehavi
A Sub-exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs
E. Grädel, S. Schalthöfer
Choiceless Logarithmic Space
12:00 - 14:00
14:00 - 15:40 5A - Parameterized Algorithms II 5B - Logic II + Approximation
R. Červený, O. Suchy
Faster FPT Algorithm for 5-Path Vertex Cover
V. Lagerkvist, G. Nordh
On the Strength of Uniqueness Quantification in Primitive Positive Formulas
D. Knop, T. Masařík, T. Toufar
Parameterized Complexity of Fair Vertex Evaluation Problems
M. Garlík
Resolution Lower Bounds for Refutation Statements
L. Jaffke, P. Thome de Lima
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs
E. Fluck
Tangles and Single Linkage Hierarchical Clustering
A. Agrawal, P. Jain, L. Kanesh, S. Saurabh
Parameterized Complexity of Conflict-Free Matchings and Paths
I. Haviv
Approximating the Orthogonality Dimension of Graphs and Hypergraphs
15:40 - 16:10
Coffee Break
16:10 - 17:30 6A - Parameterized Algorithms III 6B - Graphs, Groups and Words
C. Einarson, F. Reidl
Domination above r-independence: Does sparseness help?
M. Lohrey, A. Weiß
The power word problem
E. Galby, P. Thome de Lima, B. Ries
Reducing the domination number of graphs via edge contractions
J. Day, F. Manea, D. Nowotka
Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations
E. Eiben, R. Ganian, T. Hamm, O. Kwon
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
S. Kiefer, D. Neuen
The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs

Wednesday, August 28th
08:20 - 09:00
Registration & Refreshments
09:00 - 10:00
Invited Talk:
Daniel Lokshtanov
Picking Random Vertices
10:00 - 10:40
Coffee Break
10:40 - 12:00 7A - Complexity & Decidability I 7B - Expressability
N. Aubrun, S. Barbieri, E. Moutot
The Domino Problem is Undecidable on Surface Groups
N. Galesi, D. Itsykson, A. Riazanov, A. Sofronova
Bounded-depth Frege complexity of Tseitin formulas for all graphs
T. Dose
P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-pairs Relative to an Oracle
P. Clairambault, A. Murawski
On the expressivity of linear recursion schemes
M. Hoyrup, D. Stull
Semicomputable points in Euclidean spaces
F. Koechlin, C. Nicaud, P. Rotondo
Uniform Random Expressions Lack Expressivity
12:00 - 14:00
14:00 - 15:20 8A - Complexity & Decidability II 8B - Temporal, Geometric and
Quantum Algorithms
C. Ramya, R. Rao B V
Lower bounds for multilinear order-restricted ABPs
T. Carette, D. Horsman, S. Perdrix
SZX-calculus: Scalable Graphical Quantum Reasoning
N. Gupta, C. Saha
On the symmetries of and equivalence test for design polynomials
K. Chen, A. Dumitrescu, W. Mulzer, C. Toth
On the Stretch Factor of Polygonal Chains
J. Böker, Y. Chen, M. Grohe, G. Rattan
The Complexity of Homomorphism Indistinguishability
J. Enright, K. Meeks, G. Mertzios, V. Zamaraev
Deleting edges to restrict the size of an epidemic in temporal networks
15:20 - 16:15
Coffee Break
16:15 - 22:00

Thursday, August 29th
08:20 - 09:00
Registration & Refreshments
09:00 - 10:00
Invited Talk:
Kavitha Telikepalli
Popular Matchings: Good, Bad, and Mixed
10:00 - 10:40
Coffee Break
10:40 - 12:00 9A - Counting and Enumeration 9B - Automata and Formal Languages I
C. Berkholz, N. Schweikardt
Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width
N. Lhote, V. Michielini, M. Skrzypczak
Uniformisation gives the full strength of regular languages
A. Bulatov, A. Kazeminia
Counting Homomorphisms Modulo a Prime Number
W. Czerwiński, S. Lasota, C. Löding, R. Piórkowski
New Pumping Technique for 2-dimensional VASS
A. Bulatov, S. Živný
Approximate counting CSP seen from the other side
H. Fernau, V. V. Gusev, S. Hoffmann, M. Holzer, M. V. Volkov, P. Wolf
Computational Complexity of Synchronization under Regular Constraints
12:00 - 14:00
14:00 - 15:40 10A - Faster Algorithms 10B - Automata and Formal Languages II
T. Hagerup
A Constant-Time Colored Choice Dictionary with Almost Robust Iteration
A. Dennunzio, E. Formenti, D. Grinberg, L. Margara
Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties
S. Baswana, S. Gupta, A. Tulsyan
Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient
S. Bose, K. Shankara Narayanan, A. Muscholl, V. Penelle, G. Puppis
On Synthesis of Resynchronizers for Transducers
R. Clifford, P. Gawrychowski, T. Kociumaka, D. Martin, P. Uznański
RLE edit distance in near optimal time
P. Bell, M. Hirvensalo
Acceptance Ambiguity for Quantum Automata
S. Chakraborty, K. Sadakane
Indexing Graph Search Trees and Applications
P. Bille, I. Li Gørtz
From Regular Expression Matching to Parsing
15:40 - 16:10
Coffee Break
16:10 - 17:30 11A - Combinatorial Algorithms 11B - Automata and Formal Languages III
E. Aichinger
Solving systems of equations in supernilpotent algebras
T. Lopez, B. Monmege, J. Talbot
Determinisation of Finitely-Ambiguous Copyless Cost Register Automata
A. Conte, R. Grossi, M. Moustapha Kanté, A. Marino, T. Uno, K. Wasa
Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs
M. Droste, P. Gastin
Aperiodic Weighted Automata and Weighted First-Order Logic
S. Gaspers, R. Li
Enumeration of Preferred Extensions in Almost Oriented Digraphs
P. Ganty, E. Gutiérrez, P. Valero
A Congruence-based Perspective on Automata Minimization Algorithms

Friday, August 30th
08:20 - 09:00
Registration & Refreshments
09:00 - 10:00
Invited Talk:
Jérôme Leroux
Petri Net Reachability Problem
10:00 - 10:40
Coffee Break
10:40 - 12:00 12A - Reconfiguration problems 12B - Matrices
E. Burjons Pujol, F. Frei, E. Hemaspaandra, D. Komm, D. Wehner
Finding Optimal Solutions With Neighborly Help
C. Carlson, K. Chandrasekaran, H. Chang, N. Kakimura, A. Kolla
Spectral Aspects of Symmetric Matrix Signings
H. Mizuta, T. Hatanaka, T. Ito, X. Zhou
Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
S. Kiefer, C. Widdershoven
Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques
M. Bonamy, N. Bousquet, M. Heinrich, T. Ito, Y. Kobayashi, A. Mary, M. Muehlenthaler, K. Wasa
The Perfect Matching Reconfiguration Problem
P. Bell, I. Potapov, P. Semukhin
On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond
12:00 - 14:00
14:00 - 19:00 Workshops

Important Dates

Paper submission deadline:    Monday, April 22nd, 2019 (AoE)   
Notification of authors: Wednesday, June 12th, 2019   
Early registration deadline: Sunday, July 7th   
Standard registration deadline: Wednesday, July 31st   
Conference dates: August 26th–30th, 2019

Contact: Peter Rossmanith mfcs2019@cs.rwth-aachen.de Privacy Policy