43rd International Symposium on

Mathematical Foundations of Computer Science

August 27-31, 2018, Liverpool (UK)

MFCS 2018 is organized in coopperation with EATCS

Important Dates
Abstract submission deadline:
Friday, 20th April, 2018
Paper submission deadline:
Tuesday, 24th April, 2018
Notification of authors:
Tuesday, 12th June, 2018
Registration deadline (early):
Monday, 25th June, 2018
Registration deadline (standard):
Friday, 20th July, 2018
Conference dates:
27th-31st August, 2018


Conference Program

Program Overview

Monday Tuesday Wednesday Thursday Friday
time (August 27th) (August 28th) (August 29th) (August 30th) (August 31st)
08:20-08:50 Registration Registration & Refreshments
09:00-10:00 Invited Talk:
Christos H. Papadimitriou
Invited Talk:
Christel Baier
Invited Talk:
Olivier Bournez
Invited Talk:
Leslie Ann Goldberg
Invited Talk:
Herbert Edelsbrunner
10:00-10:30 Coffee Break
10:30-12:10 Session 1A/1B Session 4A/4B Session 7A/7B Session 9A/9B Session 12A/12B
12:15-14:00 Lunch
14:00-15:40 Session 2A/2B Session 5A/5B Session 8A/8B Session 10A/10B
Coffee Break
15:40-16:10 Coffee Break Coffee Break
16:10-17:25 Session 3A/3B Session 6A/6B Session 11A/11B


Detailed Schedule

MONDAY, August 27th
08:20-08:50 Registration Desk Opens
Christos H. Papadimitriou
Chair: Paul Spirakis
10:00-10:30 Coffee Break
Session 1A - Graphs

Session 1B - Quantum computing

10:30-10:55 Naonori Kakimura, Naoyuki Kamiyama and Kenjiro Takazawa.
The $b$-branching Problem in Digraphs
Bill Fefferman and Shelby Kimmel
Quantum vs. Classical Proofs and Subset Verification
10:55-11:20 Pavol Hell, Jing Huang, Ross McConnell and Arash Rafiey
Interval-Like Graphs and Digraphs
Francois Le Gall, Tomoyuki Morimae, Harumichi Nishimura and Yuki Takeuchi
Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups
11:20-11:45 Peter Hamburger, Ross McConnell, Attila Por, Jeremy Spinrad and Zhisheng Xu
Double Threshold Digraphs
Marco Aldi, Niel De Beaudrap, Sevag Gharibian and Seyran Saeedi
On efficiently solvable cases of Quantum k-SAT
11:45-12:10 Jakub Gajarský and Dan Kral
Recovering sparse graphs
Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram and Justin Yirka
Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
12:10-14:00 Lunch
Session 2A – Temporal Graphs & Graph Traversals

Session 2B - Logic and Semantics

14:00-14:25 Thomas Erlebach and Jakob T. Spooner
Faster Exploration of Degree-Bounded Temporal Graphs
Martin Lück
On the Complexity of Team Logic and its Two-Variable Fragment
14:25-14:50 Philipp Zschoche, Till Fluschnik, Hendrik Molter and Rolf Niedermeier
The Complexity of Finding Small Separators in Temporal Graphs
Erik Paul and Manfred Droste
A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic
14:50-15:15 Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani, Daniël Paulusma and Viktor Zamaraev
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal
Andreas Krebs, Arne Meier, Jonni Virtema and Martin Zimmermann
Team Semantics for the Specification and Verification of Hyperproperties
15:15-15:40 Mozhgan Pourmoradnasseri, Mamadou Kantéand Kaveh Khoshkhah
Enumerating Minimal Transversals of Hypergraphs Without Small Holes
Guillaume Burel
Linking Focusing and Resolution with Selection
15:40-16:10 Coffee Break
Session 3A - Optimization and Approximation

Session 3B - Computational Complexity

16:10-16:35 Vinodchandran Variyam, A Pavan and Peter Dixon
On Pseudodeterministic Approximation Algorithms
Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski and Osamu Watanabe
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction
16:35-17:00 Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang and Yuchen Zhou
Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations
Egor Klenin and Alexander Kozachinskiy
One-sided error communication complexity of Gap Hamming Distance
17:00-17:25 Ioannis Lamprou, Russell Martin, Sven Schewe, Ioannis Sigalas and Vassilis Zissimopoulos
Maximum Rooted Connected Expansion
Yassine Hamoudi
Simultaneous Multiparty Communication Protocols for Composed Functions


TUESDAY, August 28th
8:30-9:00 Registration & Refreshments
Christel Baier
chair: James Worrell
10:00-10:30 Coffee Break
Session 4A – Graph Minors and Dominating Sets

Session 4B - Automata and Languages

10:30-10:55 Argyrios Deligkas and Reshef Meir
Directed Graph Minors and Serial-Parallel Width
Louis-Marie Dando and Sylvain Lombardy
On Hadamard Series and Rotating Q-Automata
10:55-11:20 Benjamin Moore, Naomi Nishimura and Vijay Subramanya
Reconfiguration of graph minors
Andrzej Murawski, Steven Ramsay and Nikos Tzevelekos
Polynomial-time equivalence testing for deterministic fresh-register automata
11:20-11:45 Remy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim and Michael Lampis
New Results on Directed Edge Dominating Set
Moses Ganardi, Artur Jeż and Markus Lohrey
Sliding windows over context-free languages
11:45-12:10 Sayan Bandyapadhyay, Anil Maheshwari, Saeed Mehrabi and Subhash Suri
Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames
Matthew Hague, Roland Meyer, Sebastian Muskalla and Martin Zimmermann
Parity to Safety in Polynomial Time for Pushdown and Collapsible Pushdown Systems
12:10-14:00 Lunch
Session 5A – Counting and Satisfiability

Session 5B - Strings and Words

14:00-14:25 Florent Madelaine and Barnaby Martin
Consistency for counting quantifiers
P. Madhusudan, Dirk Nowotka, Aayush Rajasekaran and Jeffrey Shallit
Lagrange’s Theorem for Binary Squares
14:25-14:50 Andreas Göbel, J. A. Gregor Lagodzinski and Karen Seidel
Counting Homomorphisms to Trees Modulo a Prime
Pawel Gawrychowski, Gad Landau and Tatiana Starikovskaya
Fast entropy-bounded string dictionary look-up with mismatches
14:50-15:15 Peter Jonsson and Victor Lagerqvist
Why are CSPs Based on Partition Schemes Computationally Hard?
Laurent Bulteau and Markus L. Schmid
Consensus Strings with Small Maximum Distance and Small Distance Sum
15:15-15:40 Martin Dietzfelbinger, Philipp Schlag and Stefan Walzer
A Subquadratic Algorithm for 3XOR
Léo Exibard, Emmanuel Filiot and Ismaël Jecker
The Complexity of Transducer Synthesis from Multi-Sequential Specifications
15:40-16:10 Coffee Break
Session 6A - Optimization and Approximation

Session 6B - Computational Complexity

16:10-16:35 Francesco Cellinese, Gianlorenzo D'Angelo, Gianpiero Monaco and Yllka Velaj
Generalized budgeted submodular set function maximization
Manuel Bodirsky, Marcello Mamino, Barnaby Martin and Antoine Mottet
The complexity of disjunctive linear Diophantine constraints
16:35-17:00 Vittorio Bilò, Michele Flammini, Gianpiero Monaco and Luca Moscardelli
Pricing Problems with Buyer Preselection
Mikhail Andreev, Gleb Posobin and Alexander Shen
Plain stopping time and conditional complexities revisited
17:00-17:25 Mareike Dressler, Adam Kurpisz and Timo de Wolff
Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials
Ralph Bottesch
On W[1]-Hardness as Evidence for Intractability


WEDNESDAY, August 29th
8:30-9:00 Registration & Refreshments
Olivier Bournez
chair: Igor Potapov
10:00-10:30 Coffee Break
Session 7A – Scheduling and Packing

Session 7B - Games

10:30-10:55 Spyros Angelopoulos, Christoph Dürr and Shendan Jin
Online Maximum Matching with Recourse
Guy Avni, Shibashis Guha and Orna Kupferman
Timed Network Games with Clocks
10:55-11:20 Kelin Luo, Thomas Erlebach and Yinfeng Xu
Car-Sharing between Two Locations: Online Scheduling with Two Servers
Dan Hefetz, Orna Kupferman, Amir Lellouche and Gal Vardi
Spanning-Tree Games
11:20-11:45 Hugo Akitaya, Matthew Jones, David Stalfa and Csaba Toth
Maximum Area Axis-Aligned Square Packings
Stephane Le Roux
Concurrent games and semi-random determinacy
11:45-12:10 Aris Filos-Ratsikas, Søren Stiil Frederiksen, Paul Goldberg and Jie Zhang
Hardness Results for Consensus-Halving
Matthew Hague and Arnaud Carayol
Optimal Strategies in Pushdown Reachability Games
12:10-14:00 Lunch
Session 8A – Algorithms and Data Structures

Session 8B - Security and Learning

14:00-14:25 Dani Dorfman, Haim Kaplan, Laszlo Kozma and Uri Zwick
Pairing heaps: the forward variant
Paolo D'Arco, Roberto De Prisco, Alfredo De Santis, Ángel Pérez Del Pozo and Ugo Vaccaro
Probabilistic Secret Sharing
14:25-14:50 Frank Kammer and Andrej Sajenko
Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays
Hasan Abasi
Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph
14:50-15:20 Coffee Break


THURSDAY, August 30th
8:30-9:00 Registration & Refreshments
Leslie Ann Goldberg
10:00-10:30 Coffee Break
Session 9A – Graphs

Session 9B - Circuit Complexity

10:30-10:55 Cedric Berenger, Peter Niebert and Kevin Perrot
Balanced connected partitioning of unweighted grid graphs
Titus Dose
Balance Problems for Integer Circuits
10:55-11:20 Christian Doczkal and Damien Pous
Treewidth-Two Graphs as a Free Algebra
Pawel Idziak, Piotr Kawałek and Jacek Krzaczkowski
Expressive power, satisfiability and equivalence of circuits over nilpotent algebras
11:20-11:45 Pinar Heggernes, Davis Issac, Juho Lauri Paloma de Lima and Erik Jan van Leeuwen
Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs
Ninad Rajgopal, Rahul Santhanam and Srikanth Srinivasan
Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds
11:45-12:10 Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi and Luca Versari
Listing Subgraphs by Cartesian Decomposition
Kazuyuki Amano
Depth Two Majority Circuits for Majority and List Expanders
12:10-14:00 Lunch
Session 10A – Graphs

Session 10B - Automata and Languages

14:00-14:25 Martin Grohe, Gaurav Rattan and Gerhard J. Woeginger
Graph Similarity and Approximate Isomorphism
Mikhail Berlinkov, Robert Ferens and Marek Szykuła
Complexity of Preimage Problems for Deterministic Finite Automata
14:25-14:50 Alexander Kozachinskiy
From expanders to hitting distributions and simulation theorems
Costanza Catalano and Raphaël M. Jungers
On randomized generation of slowly synchronizing automata
14:50-15:15 Christian Konrad
A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms
Andrew Ryzhikov and Marek Szykuła
Finding Short Synchronizing Words for Prefix Codes
15:15-15:40 Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Saket Saurabh and Daniel Lokshtanov
Conflict Free Feedback Vertex Set: A Parameterized Dichotomy
Lukas Fleischer and Manfred Kufleitner
Testing Simon’s congruence
15:40-16:10 Coffee Break
Session 11A - Mobile and Distributed algorithms

Session 11B - Computational Complexity

16:10-16:35 Andreas Bärtschi, Daniel Graf and Matúš Mihalák
Collective fast delivery by energy-efficient agents
Donald Stull and Neil Lutz
Projection Theorems Using Effective Dimension
16:35-17:00 Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph and Christian Scheideler
Shape Recognition by a Finite Automaton Robot
Jenish C Mehta
Tree Tribes and lower bounds for Switching Lemmas
17:00-17:25 Aris Pagourtzis and Tomasz Radzik
Tight bounds for deterministic $h$-shot broadcast in ad-hoc directed radio networks
Donald Stull
Results on the Dimension Spectra of Planar Lines


FRIDAY, August 31st
8:30-8:55 Registration & Refreshments
Herbert Edelsbrunner
chair: Vitaliy Kurlin
10:00-10:30 Coffee Break
Session 12A – Analysis of Algorithms

Session 12B - Networks and Distributed Algorithms

10:30-10:55 Akitoshi Kawamura, Holger Thies and Martin Ziegler
Average-case polynomial-time computability of Hamiltonian dynamics
Ran Ben Basat, Gil Einziger and Roy Friedman
Give Me Some Slack: Efficient Sliding Window Measurements
10:55-11:20 Louisa Seelbach Benkner and Markus Lohrey
Average case analysis of leaf-centric binary tree sources
Hendrik Fichtenberger and Yadu Vasudev
A Two-Sided Error Distributed Property Tester For Conductance
11:20-11:45 Andre Droschinsky, Nils Kriege and Petra Mutzel
Largest Weight Common Subtree Embeddings with Distance Penalties
Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale and Giacomo Scornavacca
A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors
12:00-13:30 Lunch

Contact: Igor Potapov