41st International Symposium on

Mathematical Foundations of Computer Science

August 22-26, 2016, Krakow (Poland)

MFCS-16 is organized in coopperation with EATCS


Accepted Papers

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

Contact: Piotr Faliszewski