42nd International Symposium on

Mathematical Foundations of Computer Science

August 21-25, 2017, Aalborg (Denmark)

MFCS-17 is organized in coopperation with EATCS


Accepted Papers

The following papers are accepted for presentation at MFCS-2017

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie and Shadab Romani. Does Looking Inside a Circuit Help?
Nathan Grosshans, Pierre McKenzie and Luc Segoufin. The power of programs over monoids in DA
Kelly Yancey, Austin Parker and Matthew Yancey. Regular Language Distance and Entropy
Peter Fulla and Stanislav Živný. The complexity of Boolean surjective general-valued CSPs
Bruno Durand and Andrei Romashchenko. On the expressive power of quasi-periodic SFT
Ivan Bliznets and Nikolai Karpov. Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
Thijs Laarhoven. Hypercube LSH for approximate near neighbors
Akinori Kawachi, Mitsunori Ogihara and Kei Uchizawa. Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems
Peter Damaschke. Dividing Splittable Goods Evenly and With Limited Fragmentation
Yuka Tanimura, Takaaki Nishimoto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda. Small-space LCE data structure with constant-time queries
Renaud Vilmart, Emmanuel Jeandel, Simon Perdrix and Quanlong Wang. ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T quantum mechanics
Christoph Haase, Stefan Kiefer and Markus Lohrey. Counting Problems for Parikh Images
Sudeshna Kolay, Fahad Panolan and Saket Saurabh. Communication Complexity of Pairs of Graph Families with Applications
Erik Paul. Monitor Logics for Quantitative Monitor Automata
Hartmut Klauck. The Complexity of Quantum Disjointness
Xiaotie Deng, Yansong Gao and Jie Zhang. Smoothed and Average-case Approximation Ratios of Mechanisms: Beyond the Worst-case Analysis
Peter Jonsson, Victor Lagerqvist and Biman Roy. Time Complexity of Constraint Satisfaction via Universal Algebra
Joel Day, Florin Manea and Dirk Nowotka. The Hardness of Solving Simple Word Equations
Laure Daviaud, Pierre Guillon and Glenn Merlet. Comparison of max-plus automata and joint spectral radius of tropical matrices
Argyrios Deligkas, George Mertzios and Paul Spirakis. Binary Search in Graphs Revisited
Bart Jacobs and Fabio Zanasi. A Formal Semantics of Influence in Bayesian Reasoning
Ping Lu, Zhilin Wu and Haiming Chen. The Complexity of SORE-definability Problem
Alexei Miasnikov and Armin Weiss. TC^0 circuits for algorithmic problems in nilpotent groups
Eric Allender, Andreas Krebs and Pierre McKenzie. Better Complexity Bounds for Cost Register Machines
Jean-Daniel Boissonnat, Kunal Dutta, Arijit Ghosh and Sudeshna Kolay. Kernelization of the Subset General Position problem in Geometry
Ludmila Glinskih and Dmitry Itsykson. Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
Barnaby Martin, Catarina Carvalho and Dmitry Zhuk. The complexity of quantified constraints using the algebraic formulation
Marcelo Mydlarz, Martin Milanic and Peter Muršič. Induced embeddings into Hamming graphs
Fedor Fomin, Petr Golovach and Dimitrios Thilikos. Structured Connectivity Augmentation
Katrin Casel, Henning Fernau, Alexander Grigoriev, Markus L. Schmid and Sue Whitesides. Combinatorial Properties and Recognition of Unit Square Visibility Graphs
Manfred Droste, Stefan Dück, Dino Mandrioli and Matteo Pradella. Weighted Operator Precedence Languages
Lauri Hella, Antti Kuusisto, Arne Meier and Jonni Virtema. Model checking and validity in propositional and modal inclusion logics
Dominik Barth, Moritz Beck, Titus Dose, Christian Glasser, Larissa Michler and Marc Technau. Emptiness Problems for Integer Circuits
Benoît Monin and Paul-Elliot Anglès D'Auriac. Another characterization of the higher K-Trivials
Samson Abramsky, Rui Soares Barbosa, Nadish de Silva and Octavio Zapata. The quantum monad on relational structures
Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak and M. S. Ramanujan. Towards a Polynomial Kernel for Directed Feedback Vertex Set
Guy Avni, Shibashis Guha and Orna Kupferman. Timed Network Games
Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay and S Raja. Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings
Krishnendu Chatterjee, Monika Henzinger and Alexander Svozil. Faster Algorithms for Mean-Payoff Parity Games
Michalina Dżyga, Robert Ferens, Vladimir Gusev and Marek Szykuła. Attainable values of reset thresholds
Guillaume Lagarde, Nutan Limaye and Srikanth Srinivasan. Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees
Michał Pilipczuk, Erik Jan van Leeuwen and Andreas Wiese. Approximation and parameterized algorithms for geometric independent set with shrinking
Henning Urbat, Jiri Adamek, Liang-Ting Chen and Stefan Milius. Eilenberg Theorems for Free
Pavel Semukhin and Igor Potapov. Membership problem in GL(2,Z) extended by singular matrices
Härmel Nestra. Grammars for Indentation-Sensitive Parsing
George Mertzios, André Nichterlein and Rolf Niedermeier. The Power of Data Reduction for Matching
Michael Hoffmann and Csaba Toth. Two-Planar Graphs Are Quasiplanar
Laure Daviaud and Marianne Johnson. The Shortest Identities for Max-Plus Automata with Two States
Mohamed Faouzi Atig, Roland Meyer, Sebastian Muskalla and Prakash Saivasan. On the Upward/Downward Closures of Petri Nets
Chloe Ching-Yun Hsu and Chris Umans. On Multidimensional and Monotone k-SUM
Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou. Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
Thomas Colcombet and Daniela Petrisan. Automata in the Category of Glued Vector Spaces
Erik Paul. The Equivalence, Unambiguity and Sequentiality Problems of Finitely Ambiguous Max-Plus Tree Automata are Decidable
Eric Allender and Shuichi Hirahara. New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems
Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen and Rasmus Ibsen-Jensen. Strategy Complexity of Concurrent Safety Games
Filippo Cavallari, Henryk Michalewski and Michał Skrzypczak. A characterisation of Pi^0_2 regular tree languages
Palash Dey and Neeldhara Misra. On the Exact Amount of Missing Information that makes Finding Possible Winners Hard
Neil Lutz. Fractal Intersections and Products via Algorithmic Dimension
Matthew Hague, Roland Meyer and Sebastian Muskalla. Domains for Higher-Order Games
Akanksha Agrawal. Fine-grained Complexity of Rainbow Coloring and its Variants
Krishnendu Chatterjee, Rasmus Ibsen-Jensen and Martin A. Nowak. Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs
Tomoyuki Yamakami. The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
Neil Ghani, Conor Mcbride, Fredrik Nordvall Forsberg and Stephan Alexander Spahn. Variations on inductive-recursive definitions
Emanuel Kieronski and Antti Kuusisto. One-Dimensional Logic over Trees
Shaohua Li, Qilong Feng, Xiangzhong Meng and Jianxin Wang. An Improved Fixed-parameterized Algorithm for Parameterized Flip Distance Problem
Paul Brunet. Reversible Kleene Lattices
Ramanujan M. S., Danny Hermelin and Eduard Eiben. Lossy Kernels for Hitting Subgraphs
David Kahn. Undecidable Problems for Probabilistic Network Programming
Narayan Vikas. Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
Marthe Bonamy, Konrad Kazimierz Dabrowski, Carl Feghali, Matthew Johnson and Daniel Paulusma. Recognizing Graphs Close to Bipartite Graphs
Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Parameterized Algorithms and Kernels for Rainbow Matching
Ruggero Lanotte, Massimo Merro and Simone Tini. Compositional weak metrics for group key update
Alexandre Blanché, Konrad Kazimierz Dabrowski, Matthew Johnson, Vadim Lozin, Daniel Paulusma and Viktor Zamaraev. Clique-Width for Graph Classes Closed under Complementation
Meena Mahajan, Prajakta Nimbhorkar and Anuj Tawari. Computing the maximum using (min,+) formulas
Gianlorenzo D'Angelo, Lorenzo Severini and Yllka Velaj. Selecting nodes and buying links to maximize the information diffusion in a network
Enric Cosme Llópez and Damien Pous. K4-free graphs as a free algebra
Krishna S., Khushraj Madnani and Paritosh Pandya. Making Metric Temporal Logic Rational
S. Akshay, Nikhil Balaji and Nikhil Vyas. Complexity of restricted variants of Skolem and related problems
Irene Muzi, Michael P. O'Brien, Felix Reidl and Blair D. Sullivan. Being even slightly shallow makes life hard
Simina Branzei, Aris Filos-Ratsikas, Peter Bro Miltersen and Yulong Zeng. Optimal Walrasian Pricing in Multi-unit Auctions

Contact: Giovanni Bacci