41st International Symposium on

Mathematical Foundations of Computer Science

August 22-26, 2016, Krakow (Poland)

MFCS-16 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:15-10:30 Session 1A/1B Session 5A/5B Session 9A/9B Session 10A/10B
10:30-11:00 Coffee Break
11:00-12:00 Invited Talk:
Shai Ben-David
Invited Talk:
Tobias Friedrich
Invited Talk:
Virginia Vassilevska Williams
Invited Talk:
Patricia Bouyer-Decitre
Session 14A/14B
12:00-13:30 Lunch
Invited Talk:
Mikołaj Bojańczyk
13:30-14:45 Session 2A/2B Session 6A/6B Session 11A/11B
14:45-15:15 Coffee Break Coffee Break
15:15-16:30 Session 3A/3B Session 7A/7B Conference Trip Session 12A/12B
16:30-16:50 Coffee Break Coffee Break
16:50-18:05 Session 4A/4B Session 8A/8B Session 13A/13B
After the Opening Conference
Talks Reception Dinner

Monday (August 22nd)


Session 1A (Economics and Computation I)
81. Structural Control in Weighted Voting Games
Anja Rey and Jörg Rothe
51. The Ground-Set-Cost 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 Limit-Average 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:00-12:00: Invited Talk by Shai Ben-David

How Far Are We From Having a Satisfactory Theory of Clustering?


Session 2A (Graph Algorithms I)
35. A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion
Eduard Eiben, Robert Ganian and O-Joung 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 Bottom-up Parsing
Paola Quaglia
19. Stable states of Perturbed Markov Chains
Volker Betz and Stephane Le Roux


Session 3A (Compressed Data)
70. Shortest Unique Substring Queries on Run-Length 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 Two-dimensional Robot Games
Reino Niskanen, Igor Potapov and Julien Reichert


Session 4A (Biologically Motivated Problems)
54. Minimal Phylogenetic Supertrees and Local Consensus Trees
Jesper Jansson and Wing-Kin 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)


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 abelian-2-avoidable
Matthieu Rosenfeld

11:00-12:00: Invited Talk by Tobias Friedrich

Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms


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 Low-degree 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


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. Two-Variable 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


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 (Tree-Like 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. Transducer-based Rewriting Games for Active XML
Martin Schuster
66. Uniformization Problems for Tree-automatic Relations and Top-down Tree Transducers
Christof Löding and Sarah Winter

Wednesday (August 24th)


Session 9A (Graph Properties)
18. Graph properties in node-query 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:00-12:00: Invited Talk by Virginia Vassilevska Williams

RNA-Folding - From Hardness to Algorithms

Thursday (August 25th)


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:00-12:00: Invited Talk by Patricia Bouyer-Decitre

Optimal Reachability in Weighted Timed Automata and Games


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 first-order 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


Session 12A (Graph Algorithms III)
42. On the Complexity Landscape of Connected f-factor Problems
Robert Ganian, N.S. Narayanaswamy, Sebastian Ordyniak, C.S. Rahul and Ramanujan M. S.
36. Preprocessing under uncertainty: Matroid intersection
Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch and Vuong Anh Quyen
88. Finding a Maximum 2-Matching 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 Multi-Prover 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


Session 13A (Satisfiability Problems)
17. On the Sensitivity Conjecture for Read-k 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 1-in-3-SAT
Victor Lagerkvist and Biman Roy
Session 13B (Space-Efficient Computation)
29. Space-efficient Approximation Scheme for Maximum Matching in Sparse Graphs
Samir Datta, Raghav Kulkarni and Anish Mukherjee
57. Space-Efficient 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)


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 Mallmann-Trenn and Emanuele Natale
58. Multi-Party 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:15-14:15: Invited Talk by Mikołaj Bojańczyk

Decidable Extensions of MSO

Contact: Piotr Faliszewski