MFCS16 is organized in coopperation
with EATCS




Conference Schedule
The schedule of the conference is as follows. Talks for Sessions A will be in room 1.38 and talks
for Sessions B will be in room 2.41. Invited talks are in the same room as Sessions A.

Monday 
Tuesday 
Wednesday 
Thursday 
Friday 
time 
(August 22nd) 
(August 23rd) 
(August 24th) 
(August 25th) 
(August 26th) 
9:1510:30 
Session 1A/1B 
Session 5A/5B 
Session 9A/9B 
Session 10A/10B 
10:3011:00 
Coffee Break 
11:0012:00 
Invited Talk: Shai BenDavid 
Invited Talk: Tobias Friedrich 
Invited Talk: Virginia Vassilevska Williams 
Invited Talk: Patricia BouyerDecitre 
Session 14A/14B (11:0012:15) 



12:0013:30 
Lunch 


Invited Talk: Mikołaj Bojańczyk (13:1514:15) 
13:3014:45 
Session 2A/2B 
Session 6A/6B 

Session 11A/11B 


14:4515:15 
Coffee Break 

Coffee Break 

15:1516:30 
Session 3A/3B 
Session 7A/7B 
Conference Trip 
Session 12A/12B 

16:3016:50 
Coffee Break 

Coffee Break 

16:5018:05 
Session 4A/4B 
Session 8A/8B 

Session 13A/13B 

After the 
Opening 


Conference 

Talks 
Reception 


Dinner 

Monday (August 22nd)
9:1510:30
Session 1A (Economics and Computation I)
81.  Structural Control in Weighted Voting Games 
 Anja Rey and Jörg Rothe 
 
51.  The GroundSetCost Budgeted Maximum Coverage Problem 
 Irving van Heuven van Staereling, Bart de Keijzer and Guido Schaefer 
 
90.  An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Tour Length 
 Mingyu Xiao and Shaowei Kou 
 
Session 1B (Automata I)
68.  Piecewise Testable Languages and Nondeterministic Automata 
 Tomas Masopust 
 
25.  Nested Weighted LimitAverage Automata of Bounded Width 
 Krishnendu Chatterjee, Thomas Henzinger and Jan Otop 
 
62.  On the Complexity of Universality for Partially Ordered NFAs 
 Markus Krötzsch, Tomas Masopust and Michaël Thomazo 
 
11:0012:00: Invited Talk by Shai BenDavid
How Far Are We From Having a Satisfactory Theory of Clustering?
13:3014:45
Session 2A (Graph Algorithms I)
35.  A SingleExponential FixedParameter Algorithm for DistanceHereditary Vertex Deletion 
 Eduard Eiben, Robert Ganian and OJoung Kwon 
 
14.  The parameterized complexity of fixing number and vertex individualization in graphs 
 Vikraman Arvind, Frank Fuhlbrueck, Johannes Koebler, Sebastian Kuhnert and Gaurav Rattan 
 
21.  Using Contracted Solution Graphs for Solving Reconfiguration Problems 
 Paul Bonsma and Daniel Paulusma 
 
session 2B (Automata II)
16.  Synchronizing Data Words for Register Automata 
 Parvaneh Babari, Karin Quaas and Mahsa Shirmohammadi 
 
80.  Symbolic Lookaheads for Bottomup Parsing 
 Paola Quaglia 
 
19.  Stable states of Perturbed Markov Chains 
 Volker Betz and Stephane Le Roux 
 
15:1516:30
Session 3A (Compressed Data)
70.  Shortest Unique Substring Queries on RunLength Encoded Strings 
 Takuya Mieno, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda 
 
73.  Fully dynamic data structure for LCE queries in compressed space 
 Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda 
 
31.  Ackermannian integer compression and the word problem for hydra groups 
 Will Dison, Eduard Einstein and Timothy Riley 
 
Session 3B (Games in Verification)
26.  Conditionally Optimal Algorithms for Generalized Büchi Games 
 Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger and Veronika Loitzenbauer 
 
9.  Stochastic Timed Games Revisited 
 S. Akshay, Patricia Bouyer, Krishna S., Lakshmi Manasa and Ashutosh Trivedi 
 
74.  Undecidability of Twodimensional Robot Games 
 Reino Niskanen, Igor Potapov and Julien Reichert 
 
16:5018:05
Session 4A (Biologically Motivated Problems)
54.  Minimal Phylogenetic Supertrees and Local Consensus Trees 
 Jesper Jansson and WingKin Sung 
 
38.  On the General Chain Pair Simplification Problem 
 Chenglin Fan, Omrit Filtser, Matthew Katz and Binhai Zhu 
 
34.  Faster Algorithms for the Maximum Common Subtree Isomorphism Problem 
 Andre Droschinsky, Nils Kriege and Petra Mutzel 
 
Session 4B (Computability)
87.  Polynomial Space Randomness in Analysis 
 Donald Stull and Xiang Huang 
 
59.  Dividing by zero  how bad is it, really? 
 Takayuki Kihara and Arno Pauly 
 
77.  Supplementarity is Necessary for Quantum Diagram Reasoning 
 Simon Perdrix and Quanlong Wang 
 
Tuesday (August 23rd)
9:1510:30
Session 5A (Graph Algorithms II)
8.  Routing with Congestion in Acyclic Digraphs 
 Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx and Roman Rabinovich 
 
76.  Parameterized Algorithms on Perfect Graphs for deletion to (r, l)graphs 
 Fahad Panolan, Sudeshna Kolay, Venkatesh Raman and Saket Saurabh 
 
27.  FPT Algorithms for Plane Completion Problems 
 Dimitris Chatzidimitriou, Archontia Giannopoulou, Spyridon Maniatis, Clément Requilé, Dimitrios Thilikos and Dimitris Zoros 
 
Session 5B (Word Combinatorics)
41.  Determining sets of quasiperiods of infinite words 
 Guilhem Gamard and Gwenaël Richomme 
 
52.  Computational and proof complexity of partial string avoidability 
 Dmitry Itsykson, Alexander Okhotin and Vsevolod Oparin 
 
82.  Every binary pattern of length greater than 14 is abelian2avoidable 
 Matthieu Rosenfeld 
 
11:0012:00: Invited Talk by Tobias Friedrich
ScaleFree Networks, Hyperbolic Geometry, and Efficient Algorithms
13:3014:45
Session 6A (CSPs)
40.  On Planar Valued CSPs 
 Peter Fulla and Stanislav Živný 
 
33.  Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers 
 Titus Dose 
 
72.  Optimal Sparsification for Some Binary CSPs Using Lowdegree Polynomials 
 Bart M. P. Jansen and Astrid Pieterse 
 
session 6B (Automata and Algebra)
49.  On synchronizing colorings and the eigenvectors of digraphs 
 Vladimir Gusev and Elena Pribavkina 
 
85.  Vector Reachability Problem in SL(2,Z) 
 Pavel Semukhin and Igor Potapov 
 
45.  Connected reversible Mealy automata of prime size cannot generate infinite Burnside groups 
 Thibault Godin and Ines Klimann 
 
15:1516:30
Session 7A (Algebraic Approaches)
7.  Integer factoring using small algebraic dependencies 
 Manindra Agrawal, Nitin Saxena and Shubham Sahai Srivastava 
 
48.  Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields 
 Zeyu Guo, Anand Narayanan and Chris Umans 
 
75.  Algebraic independence over positive characteristic: New criterion and applications to locally low algebraic rank circuits 
 Anurag Pandey, Nitin Saxena and Amit Sinhababu 
 
Session 7B (Logic)
61.  Decidability of predicate logics with team semantics 
 Juha Kontinen, Antti Kuusisto and Jonni Virtema 
 
67.  TwoVariable Logic over Countable Linear Orders 
 Amaldev Manuel and A V Sreejith 
 
78.  The Covering Problem: a Unified Approach for Investigating the Expressive Power of Logics 
 Thomas Place and Marc Zeitoun 
 
16:5018:05
Session 8A (Computational Complexity)
11.  Trading Determinism for Time in Space Bounded Computations 
 Vivek Anand T Kallampally and Raghunath Tewari 
 
20.  On degeneration of tensors and algebras 
 Markus Bläser and Vladimir Lysikov 
 
28.  Some lower bounds in parameterized $\AC^0$ 
 Yijia Chen and Jörg Flum 
 
Session 8B (TreeLike and Acyclic Structures)
39.  Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets 
 Yuta Fujishige, Yuki Tsujimaru, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda 
 
84.  Transducerbased Rewriting Games for Active XML 
 Martin Schuster 
 
66.  Uniformization Problems for Treeautomatic Relations and Topdown Tree Transducers 
 Christof Löding and Sarah Winter 
 
Wednesday (August 24th)
9:1510:30
Session 9A (Graph Properties)
18.  Graph properties in nodequery setting: effect of breaking symmetry 
 Nikhil Balaji, Samir Datta, Raghav Kulkarni and Supartha Podder 
 
24.  On the Implicit Graph Conjecture 
 Maurice Chandoo 
 
64.  On the exact learnability of graph parameters: The case of partition functions 
 Nadia Labai and Johann Makowsky 
 
Session 9B (Models of Computation)
55.  Quantum Communication Complexity of Distributed Set Joins 
 Stacey Jeffery and Francois Le Gall 
 
44.  Programming biomolecules that fold greedily during transcription 
 Cody Geary, PierreÉtienne Meunier, Nicolas Schabanel and Shinnosuke Seki 
 
60.  Advice Complexity of the Online Induced Subgraph Problem 
 Dennis Komm, Rastislav Kralovic, Richard Kralovic and Christian Kudahl 
 
11:0012:00: Invited Talk by Virginia Vassilevska Williams
RNAFolding  From Hardness to Algorithms
Thursday (August 25th)
9:1510:30
Session 10A (Economics and Computation II)
10.  Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results 
 Georgios Amanatidis, Evangelos Markakis and Krzysztof Sornat 
 
37.  Ride Sharing with a Vehicle of Unlimited Capacity 
 Angelo Fanelli and Gianluigi Greco 
 
50.  Competitive Packet Routing with Priority Lists 
 Tobias Harks, Britta Peis, Daniel Schmand and Laura Vargas Koch 
 
Session 10B (Circuits, Lower Bounds)
46.  Circuit size lower bounds and #SAT upper bounds through a general framework 
 Alexander Golovnev, Alexander Kulikov, Suguru Tamaki and Alexander Smal 
 
71.  Shattered Sets and the Hilbert Function 
 Shay Moran and Cyrus Rashtchian 
 
47.  On the Limits of Gate Elimination 
 Alexander Golovnev, Edward Hirsch, Alexander Knop and Alexander Kulikov 
 
11:0012:00: Invited Talk by Patricia BouyerDecitre
Optimal Reachability in Weighted Timed Automata and Games
13:3014:45
Session 11A (Aspects of Computational Hardness)
86.  The Generalised Colouring Numbers on Classes of Bounded Expansion 
 Sebastian Siebertz, Roman Rabinovich, Stephan Kreutzer and Michał Pilipczuk 
 
43.  On Existential MSO and its Relation to ETH 
 Robert Ganian, Ronald de Haan, Iyad Kanj and Stefan Szeider 
 
63.  Eulerian Paths with Regular Constraints 
 Orna Kupferman and Gal Vardi 
 
Session 11B (Program Equivalence)
53.  Deciding semantic finiteness of pushdown processes and firstorder grammars wrt bisimulation equivalence 
 Petr Jancar 
 
30.  Logical Characterization of Bisimulation for Transition Relations over Probability Distributions with Internal Actions 
 Matias David Lee and Erik de Vink 
 
23.  An exploration of Nominal Kleene Algebra in Coq 
 Paul Brunet and Damien Pous 
 
15:1516:30
Session 12A (Graph Algorithms III)
42.  On the Complexity Landscape of Connected ffactor Problems 
 Robert Ganian, N.S. Narayanaswamy, Sebastian Ordyniak, C.S. Rahul and Ramanujan M. S. 
 
36.  Preprocessing under uncertainty: Matroid intersection 
 Stefan Fafianie, EvaMaria C. Hols, Stefan Kratsch and Vuong Anh Quyen 
 
88.  Finding a Maximum 2Matching Excluding Prescribed Cycles in Bipartite Graphs 
 Kenjiro Takazawa 
 
Session 12B (PCP/IP)
15.  Real interactive proofs for VPSPACE 
 Martijn Baartse and Klaus Meer 
 
22.  Pointer Quantum PCPs and MultiProver Games 
 Alex Bredariol Grilo, Iordanis Kerenidis and Attila Pereszlenyi 
 
13.  On the complexity of probabilistic trials for hidden satisfiability problems 
 Itai Arad, Adam Bouland, Daniel Grier, Miklos Santha, Aarthi Sundaram and Shengyu Zhang 
 
16:5018:05
Session 13A (Satisfiability Problems)
17.  On the Sensitivity Conjecture for Readk Formulas 
 Mitali Bafna, Satyanarayana V. Lokam, Sebastien Tavenas and Ameya Velingker 
 
83.  Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression 
 Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki and Junichi Teruyama 
 
65.  A Preliminary Investigation of Satisfiability Problems Not Harder than 1in3SAT 
 Victor Lagerkvist and Biman Roy 
 
Session 13B (SpaceEfficient Computation)
29.  Spaceefficient Approximation Scheme for Maximum Matching in Sparse Graphs 
 Samir Datta, Raghav Kulkarni and Anish Mukherjee 
 
57.  SpaceEfficient Biconnected Components and Recognition of Outerplanar Graphs 
 Frank Kammer, Dieter Kratsch and Moritz Laudahn 
 
32.  A Note on the Advice Complexity of Multipass Randomized Logspace 
 Peter Dixon, Debasis Mandal, A. Pavan and N. V. Vinodchandran 
 
Friday (August 26th)
11:0012:15
Session 14A (Distributed Computing)
69.  Stably Computing Order Statistics with Arithmetic Population Protocols 
 George Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis 
 
56.  On the Voting Time of the Deterministic Majority Process 
 Dominik Kaaser, Frederik MallmannTrenn and Emanuele Natale 
 
58.  MultiParty Protocols, Information Complexity and Privacy 
 Iordanis Kerenidis, Adi Rosén and Florent Urrutia 
 
Session 14B (Automata over Infinitary Structures)
89.  Transformation between regular expressions and $\omega$automata 
 Andreas Tollkötter and Christof Löding 
 
12.  Families of DFAs as Acceptors of $\omega$Regular Languages 
 Dana Angluin, Udi Boker and Dana Fisman 
 
79.  On the Complexity of Branching Games with Regular Conditions 
 Marcin Przybyłko and Michał Skrzypczak 
 
13:1514:15: Invited Talk by Mikołaj Bojańczyk
Decidable Extensions of MSO
