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

Monday Tuesday Wednesday Thursday Friday
time (August 21st) (August 22nd) (August 23rd) (August 24th) (August 25th)
9:15-9:30 Opening
9:30-10:30 Invited Talk:
Glynn Winskel
Invited Talk:
Michal 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 9A/9B Session 12C/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
9:15-9:30 Official Opening of the Conference
9:30-10:30 Glynn Winskel
Distributed strategies made easy
10:30-11:00 Coffee Break
Session 1B - Games 1 Session 1C - Circuit Complexity
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 B2 - Tree, Logic and Automata Session C2 - Circuit Complexity
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 B3 - Games 2 Session C3 - Tree width & Clique width
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
9:30-10:30 Michał Pilipczuk
On definable and recognizable properties of graphs of bounded treewidth
10:30-11:00 Coffee Break
Session 4B - FPT 1 Session 4C - Language, Automata, Parsing 1
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 B5 - FPT 2 Session C5 - Quantum Computing
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 B6 - FPT 3 Session C6 - Language and Complexity -- Kolmogorov Complexity
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
9:30-10:30 Nicolas Markey
Temporal logics for multi-agent systems
10:30-11:00 Coffee Break
Session 7B - Logic, Model Checking Session 7C - Data Structures and Algorithms
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 Session 8C - Language, Automata, Parsing 2
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
Ludmila Glinskih and Dmitry Itsykson
Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
Härmel Nestra
Grammars for Indentation-Sensitive Parsing
15:00-15:30 Coffee Break
15:45-22:00 Excursion and Conference Dinner

THURSDAY, August 24th
9:30-10:30 Rasmus Pagh
Hardness and Approximation of High-Dimensional Search Problems
10:30-11:00 Coffee Break
Session 9B - Graph Algorithms Session 9C - Programming Languages - Tiling
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 Session 10C - Constraint Satisfaction -- Logic, Model Checking
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
Barnaby Martin, Catarina Carvalho and Dmitry Zhuk
The complexity of quantified constraints using the algebraic formulation
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 Session 11C - Optimization and Mathematical Computation
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
9:30-10:30 Philippe Schnoebelen
Ideal-Based Algorithms for the Symbolic Verification of Well-Structured Systems
10:30-11:00 Coffee Break
Session 12B - Networks and Petri Nets Session 12C - Bayesian Networks -- Language, Automata, Parsing 4
Strategy Complexity of Concurrent Safety Games
A Formal Semantics of Influence in Bayesian Reasoning
Akinori Kawachi, Mitsunori Ogihara and Kei Uchizawa
Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems
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