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 |
| 12:30-13:00 |
|
|
| 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 |
| 17:00-17:30 |
|
|
|
|
| 17:30-18:00 |
|
|
|
|
| 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 |
| 9:30-10:30 |
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
|
| 11:00-11:30 |
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?
|
| 11:30-12:00 |
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
|
| 12:00-12:30 |
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
|
| 13:30-14:00 |
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
|
| 14:00-14:30 |
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
|
| 14:30-15:00 |
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
|
| 15:30-16:00 |
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
|
| 16:00-16:30 |
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
|
| 16:30-17:00 |
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
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
|
| 11:00-11:30 |
The Power of Data Reduction for Matching
|
Kelly Yancey, Austin Parker and Matthew Yancey
Regular Language Distance and Entropy
|
| 11:30-12:00 |
Lossy Kernels for Hitting Subgraphs
|
Comparison of max-plus automata and joint spectral radius of tropical matrices
|
| 12:00-12:30 |
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
|
| 13:30-14:00 |
Kernelization of the Subset General Position problem in Geometry
|
ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T quantum mechanics
|
| 14:00-14:30 |
Approximation and parameterized algorithms for geometric independent set with shrinking
|
The Complexity of Quantum Disjointness
|
| 14:30-15:00 |
Parameterized Algorithms and Kernels for Rainbow Matching
|
The quantum monad on relational structures
|
| 15:00-15:30 |
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
|
| 16:00-16:30 |
Communication Complexity of Pairs of Graph Families with Applications
|
Ping Lu, Zhilin Wu and Haiming Chen
The Complexity of SORE-definability Problem
|
| 16:30-17:00 |
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
|
| 17:00-17:30 |
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
|
| 17:30-18:00 |
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
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
|
| 11:00-11:30 |
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
|
| 11:30-12:00 |
David Kahn
Undecidable Problems for Probabilistic Network Programming
|
Hypercube LSH for approximate near neighbors
|
| 12:00-12:30 |
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
|
| 13:30-14:00 |
The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
|
Eilenberg Theorems for Free
|
| 14:00-14:30 |
The power of programs over monoids in DA
|
Membership problem in GL(2,Z) extended by singular matrices
|
| 14:30-15:00 |
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 |
| 9:30-10:30 |
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
|
| 11:00-11:30 |
Structured Connectivity Augmentation
|
Variations on inductive-recursive definitions
|
| 11:30-12:00 |
Binary Search in Graphs Revisited
|
Compositional weak metrics for group key update
|
| 12:00-12:30 |
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
|
| 13:30-14:00 |
Katrin Casel, Henning Fernau, Alexander Grigoriev, Markus L. Schmid and Sue Whitesides
Combinatorial Properties and Recognition of Unit Square Visibility Graphs
|
The complexity of Boolean surjective general-valued CSPs
|
| 14:00-14:30 |
Two-Planar Graphs Are Quasiplanar
|
Time Complexity of Constraint Satisfaction via Universal Algebra
|
| 14:30-15:00 |
Induced embeddings into Hamming graphs
|
Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs
|
| 15:00-15:30 |
Recognizing Graphs Close to Bipartite Graphs
|
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
|
| 16:00-16:30 |
Weighted Operator Precedence Languages
|
Dividing Splittable Goods Evenly and With Limited Fragmentation
|
| 16:30-17:00 |
A characterisation of Pi^0_2 regular tree languages
|
Selecting nodes and buying links to maximize the information diffusion in a network
|
| 17:00-17:30 |
Attainable values of reset thresholds
|
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
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
|
| 11:00-11:30 |
Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems
|
A Formal Semantics of Influence in Bayesian Reasoning
|
| 11:30-12:00 |
Ludmila Glinskih and Dmitry Itsykson
Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
|
Automata in the Category of Glued Vector Spaces
|
| 12:00-12:30 |
On the Upward/Downward Closures of Petri Nets
|
Better Complexity Bounds for Cost Register Machines
|
| 12:30-13:00 |
Reversible Kleene Lattices
|
Counting Problems for Parikh Images
|
| 13:00-14:00 |
Lunch |
| 14:00 |
End of the Conference |
|