42nd International Symposium on

Mathematical Foundations of Computer Science

August 21-25, 2017, Aalborg (Denmark)

MFCS-17 is organized in coopperation with EATCS


Conference Program

Program Overview

The schedule of the conference is as follows. Talks for Sessions B will be in Auditorium B and talks for Sessions C will be in Auditorum C. Invited talks are in Auditorium B. Auditoriums B and C are located in the same building across the street, opposite to Auditorium A (Fibigerstræde 15, 9220 Aalborg Øst) where the conference lunches will be served.

Monday Tuesday Wednesday Thursday Friday
time (August 21st) (August 22nd) (August 23rd) (August 24th) (August 25th)
8:30-9:15 Registration
9:15-9:30 Opening
9:30-10:30 Invited Talk:
Glynn Winskel
Invited Talk:
Michał Pilipczuk
Invited Talk:
Nicolas Markey
Invited Talk:
Rasmus Pagh
Invited Talk:
Philippe Schnoebelen
10:30-11:00 Coffee Break
11:00-12:30 Session 1B/1C Session 4B/4C Session 7B/7C Session 9B/9C Session 12B/12C
13:00-13:30 Lunch Lunch
13:30-14:00 Session 2B/2C Session 5B/5C Session 8B/8C Session 10B/10C
14:00-15:00 Closing
15:00-15:30 Coffee Break Coffee Break
15:30-16:00 Coffee Break Coffee Break
16:00-17:00 Session 3B/3C Session 6B/6C Excursion + Dinner Session 11B/11C
18:30-20:00 reception

Detailed Schedule

MONDAY, August 21st
8:30-9:15 Registration Desk Opens
9:15-9:30 Official Opening of the Conference
Glynn Winskel
Distributed strategies made easy
chair: Kim G. Larsen
10:30-11:00 Coffee Break
Session 1B - Games 1
chair: Peter van Emde Boas
Session 1C - Circuit Complexity
chair: Enric Cosme Llopez
Simina Branzei, Aris Filos-Ratsikas, Peter Bro Miltersen, and Yulong Zeng
Optimal Walrasian Pricing in Multi-unit Auctions
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, and Shadab Romani
Does Looking Inside a Circuit Help?
Xiaotie Deng, Yansong Gao, and Jie Zhang
Smoothed and Averagecase Approximation Ratios of Mechanisms
Alexei Miasnikov and Armin Weiss
TC0 circuits for algorithmic problems in nilpotent groups
Guy Avni, Shibashis Guha, and Orna Kupferman
Timed Network Game
Dominik Barth, Moritz Beck, Titus Dose, Christian Glasser, Larissa Michler, and Marc Technau
Emptiness Problems for Integer Circuits
12:30-13:30 Lunch
Session 2B - Tree, Logic and Automata
chair: Jean-François Raskin
Session 2C - Circuit Complexity
chair: Valentine Kabanets
Matthew Hague, Roland Meyer, and Sebastian Muskalla
Domains for Higher-Order Games
Eric Allender and Shuichi Hirahara
New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems
Erik Paul
The Equivalence, Unambiguity and Sequentiality Problems of Finitely Ambiguous Max-Plus Tree Automata are Decidable
Guillaume Lagarde, Nutan Limaye, and Srikanth Srinivasan
Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees
Emanuel Kieronski and Antti Kuusisto
One-Dimensional Logic over Trees
Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, and S. Raja
Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings
15:00-15:30 Coffee Break
Session 3B - Games 2
chair: Glynn Winskel
Session 3C - Tree width & Clique width
chair: Pierre McKenzie
Palash Dey and Neeldhara Misra
On the Exact Amount of Missing Information that makes Finding Possible Winners Har
Irene Muzi, Michael P. O'Brien, Felix Reidl, and Blair D. Sullivan
Being even slightly shallow makes life hard
Krishnendu Chatterjee, Monika Henzinger, and Alexander Svozil
Faster Algorithms for Mean-Payoff Parity Games
Enric Cosme Llopez and Damien Pous
K4-free graphs as a free algebra
Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen and Rasmus IbsenJensen
Strategy Complexity of Concurrent Safety Game
Alexandre Blanche, Konrad Kazimierz Dabrowski, Matthew Johnson, Vadim Lozin, Daniel Paulusma and Viktor Zamaraev
Clique-Width for Graph Classes Closed under Complementation
18:30-20:00 Welcome reception (House of Music)

TUESDAY, August 22nd
Michał Pilipczuk
On definable and recognizable properties of graphs of bounded treewidth
chair: Hans L. Bodlaender
10:30-11:00 Coffee Break
Session 4B - FPT 1
chair: Michał Pilipczuk
Session 4C - Language, Automata, Parsing 1
chair: Igor Potapov
The Power of Data Reduction for Matching
Kelly Yancey, Austin Parker and Matthew Yancey
Regular Language Distance and Entropy
Lossy Kernels for Hitting Subgraphs
Laure Daviaud, Pierre Guillon and Glenn Merlet
Comparison of max-plus automata and joint spectral radius of tropical matrices
Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak and M. S. Ramanujan
Towards a Polynomial Kernel for Directed Feedback Vertex Set
Laure Daviaud and Marianne Johnson
The Shortest Identities for Max-Plus Automata with Two States
12:30-13:30 Lunch
Session 5B - FPT 2
chair: Matthew Johnson
Session 5C - Quantum Computing
chair: Robert Furber
Kernelization of the Subset General Position problem in Geometry
ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T quantum mechanics
Approximation and parameterized algorithms for geometric independent set with shrinking
The Complexity of Quantum Disjointness
Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi
Parameterized Algorithms and Kernels for Rainbow Matching
Samson Abramsky, Rui Soares Barbosa, Nadish de Silva and Octavio Zapata
The quantum monad on relational structures
Ivan Bliznets and Nikolai Karpov
Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
Monitor Logics for Quantitative Monitor Automata
15:30-16:00 Coffee Break
Session 6B - FPT 3
chair: M. S. Ramanujan
Session 6C - Language and Complexity, Kolmogorov Complexity
chair: Rasmus IbsenJensen
Sudeshna Kolay, Fahad Panolan and Saket Saurabh
Communication Complexity of Pairs of Graph Families with Applications
Ping Lu, Zhilin Wu and Haiming Chen
The Complexity of SORE-definability Problem
Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou
Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
The Hardness of Solving Simple Word Equations
Shaohua Li, Qilong Feng, Xiangzhong Meng and Jianxin Wang
An Improved Fixed-parameterized Algorithm for Parameterized Flip Distance Problem
Fractal Intersections and Products via Algorithmic Dimension
Akanksha Agrawal.
Fine-grained Complexity of Rainbow Coloring and its Variants
Benoît Monin and Paul-Elliot Anglès D'Auriac
Another characterization of the higher K-Trivials

WEDNESDAY, August 23rd
Nicolas Markey
Temporal logics for multi-agent systems
chair: Jean-François Raskin
10:30-11:00 Coffee Break
Session 7B - Logic, Model Checking
chair: Nicolas Markey
Session 7C - Data Structures and Algorithms
chair: Giovanni Bacci
Lauri Hella, Antti Kuusisto, Arne Meier and Jonni Virtema
Model checking and validity in propositional and modal inclusion logics
Yuka Tanimura, Takaaki Nishimoto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda
Small-space LCE data structure with constant-time queries
David Kahn
Undecidable Problems for Probabilistic Network Programming
Hypercube LSH for approximate near neighbors
Making Metric Temporal Logic Rational
Computing the maximum using (min,+) formulas
12:30-13:30 Lunch
Session 8B - Complexity Theory
chair: Peter Damaschke
Session 8C - Language, Automata, Parsing 2
chair: Giorgio Bacci
The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
Henning Urbat, Jiri Adamek, Liang-Ting Chen and Stefan Milius
Eilenberg Theorems for Free
Nathan Grosshans, Pierre McKenzie and Luc Segoufin
The power of programs over monoids in DA
Pavel Semukhin and Igor Potapov
Membership problem in GL(2,Z) extended by singular matrices
Barnaby Martin, Catarina Carvalho and Dmitry Zhuk
The complexity of quantified constraints using the algebraic formulation
Härmel Nestra
Grammars for Indentation-Sensitive Parsing
15:00-15:30 Coffee Break
15:45-21:30 Excursion and Conference Dinner

THURSDAY, August 24th
Rasmus Pagh
Hardness and Approximation of High-Dimensional Search Problems
chair: Radu Mardare
10:30-11:00 Coffee Break
Session 9B - Graph Algorithms
chair: Rasmus Pagh
Session 9C - Programming Languages - Tiling
chair: Stefan Kiefer
Fedor Fomin, Petr Golovach and Dimitrios Thilikos
Structured Connectivity Augmentation
Neil Ghani, Conor Mcbride, Fredrik Nordvall Forsberg and Stephan Alexander Spahn
Variations on inductive-recursive definitions
Binary Search in Graphs Revisited
Ruggero Lanotte, Massimo Merro and Simone Tini
Compositional weak metrics for group key update
Narayan Vikas
Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
Bruno Durand and Andrei Romashchenko
On the expressive power of quasi-periodic SFT
12:30-13:30 Lunch
Session 10B - Graph Characterization and Algorithms
chair: Petr Golovach
Session 10C - Constraint Satisfaction, Logic, Model Checking
chair: Bart Jacobs
Katrin Casel, Henning Fernau, Alexander Grigoriev, Markus L. Schmid and Sue Whitesides
Combinatorial Properties and Recognition of Unit Square Visibility Graphs
Peter Fulla and Stanislav Živný
The complexity of Boolean surjective general-valued CSPs
Two-Planar Graphs Are Quasiplanar
Peter Jonsson, Victor Lagerqvist and Biman Roy
Time Complexity of Constraint Satisfaction via Universal Algebra
Marcelo Mydlarz, Martin Milanic and Peter Muršič
Induced embeddings into Hamming graphs
Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs
Marthe Bonamy, Konrad Kazimierz Dabrowski, Carl Feghali, Matthew Johnson and Daniel Paulusma
Recognizing Graphs Close to Bipartite Graphs
S. Akshay, Nikhil Balaji and Nikhil Vyas
Complexity of restricted variants of Skolem and related problems
15:30-16:00 Coffee Break
Session 11B - Languages, Automata, Parsing 3
chair: Axel Legay
Session 11C - Optimization and Mathematical Computation
chair: Michael Hoffmann
Manfred Droste, Stefan Dück, Dino Mandrioli and Matteo Pradella
Weighted Operator Precedence Languages
Dividing Splittable Goods Evenly and With Limited Fragmentation
A characterisation of Pi^0_2 regular tree languages
Gianlorenzo D'Angelo, Lorenzo Severini and Yllka Velaj
Selecting nodes and buying links to maximize the information diffusion in a network
Michalina Dżyga, Robert Ferens, Vladimir Gusev and Marek Szykuła
Attainable values of reset thresholds
Chloe Ching-Yun Hsu and Chris Umans
On Multidimensional and Monotone k-SUM

FRIDAY, August 25th
Philippe Schnoebelen
Ideal-Based Algorithms for the Symbolic Verification of Well-Structured Systems
chair: Jiří Srba
10:30-11:00 Coffee Break
Session 12B - Networks and Petri Nets
chair: Radu Mardare
Session 12C - Bayesian Networks -- Language, Automata, Parsing 4
chair: Kim G. Larsen
Akinori Kawachi, Mitsunori Ogihara and Kei Uchizawa
Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems
A Formal Semantics of Influence in Bayesian Reasoning
Ludmila Glinskih and Dmitry Itsykson
Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
Automata in the Category of Glued Vector Spaces
On the Upward/Downward Closures of Petri Nets
Eric Allender, Andreas Krebs and Pierre McKenzie
Better Complexity Bounds for Cost Register Machines
Reversible Kleene Lattices
Counting Problems for Parikh Images
13:00-14:00 Lunch
14:00 End of the Conference

Contact: Giovanni Bacci