MFCS 2019 is organized in cooperation with EATCS
|
|
|
|
Conference Program
Program Overview
|
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
| time |
(August 26th) |
(August 27th) |
(August 28th) |
(August 29th) |
(August 30th) |
| 08:20-08:50 |
Registration |
Registration & Refreshments |
| 08:50-09:00 |
Opening |
| 09:00-10:00 |
Invited Talk:
Kurt
Mehlhorn |
Invited Talk:
Alexandra
Silva |
Invited Talk:
Daniel
Lokshtanov |
Invited Talk:
Kavitha
Telikepalli |
Invited Talk:
Jérôme
Leroux |
| 10:00-10:40 |
Coffee Break |
| 10:40-12:00 |
Session 1A/1B |
Session 4A/4B |
Session 7A/7B |
Session 9A/9B |
Session 12A/12B |
| Closing |
| 12:00-14:00 |
Lunch |
| 14:00-15:40 |
Session 2A/2B |
Session 5A/5B |
Session 8A/8B |
Session 10A/10B |
Workshops:
ARDA 2019
Fri. 14:00 - 19:00
Structural Sparseness
Fri. 14:00 - 19:00
Sat. 9:00 - 16:00 |
| 15:40-16:10 |
Coffee Break |
| 16:10-17:30 |
Session 3A/3B |
Session 6A/6B |
16:30
Social Program & Conference Dinner |
Session 11A/11B |
|
17:30
Welcome reception |
|
Monday, August 26th |
| 08:20 - 08:50 |
Registration & Refreshments |
| 08:50 - 09:00 |
Opening |
| 09:00 - 10:00 |
Invited Talk:
Kurt Mehlhorn
Trustworthy Graph Algorithms |
| 10:00 - 10:40 |
Coffee Break |
| 10:40 - 12:00 |
1A - Online Algorithms |
1B - Games |
|
M. Bieńkowski, H. Liu
An Improved Online Algorithm for Traveling Repairperson Problem on a Line |
P. Bouyer, N. Thomasset
Nash equilibria in games over graphs equipped with a communication mechanism |
|
M. de Lima, M. Halldórsson
Query-Competitive Sorting with Uncertainty |
P. Parys
Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time |
|
M. Bieńkowski, J. Byrka, M. Chrobak, C. Coester, Ł. Jeż, E. Koutsoupias
Better Bounds for Online Line Chasing |
G. Avni, T. Henzinger, D. Žikelić
Bidding Mechanisms in Graph Games |
| 12:00 - 14:00 |
Lunch |
| 14:00 - 15:40 |
2A - Graph Algorithms |
2B - First-Order Logic |
|
A. Konstantinidis, C. Papadopoulos
Cluster Deletion on Interval Graphs and Split Related Graphs |
E. Kieroński
One-dimensional guarded fragments |
|
H. Le, V. Bang Le
Constrained representations of map graphs and half-squares |
D. Danielski, E. Kieroński
Finite Satisfiability of Unary Negation Fragment with Transitivity |
|
B. Martin, D. Paulusma, S. Smith
Colouring H-free Graphs of Bounded Diameter |
L. Tendera, I. Pratt-Hartmann
Fluted Fragment with Transitivity |
|
V. Chepoi, A. Labourel, S. Ratel
Distance labeling schemes for cube-free median graphs |
A. Haak, J. Kontinen, F. Müller, H. Vollmer, F. Yang
Counting of Teams in First-Order Team Logics |
| 15:40 - 16:10 |
Coffee Break |
| 16:10 - 17:30 |
3A - Approximation Algorithms |
3B - Algebraic and Differential Equations |
|
Z. Nutov, G. Kortsarz, E. Shalom
Approximating activation edge-cover and facility location problems |
O. Bournez, A. Durand
Recursion schemes, discrete differential equations and characterization of polynomial time computation |
|
C. Konrad, V. Zamaraev
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs |
M. Boreale
On the coalgebra of partial differential equations |
|
E. Bampis, B. Escoffier, A. Teiller
Multistage Knapsack |
Z. Gao, S. Jain, B. Khoussainov, W. Li, A. Melnikov, K. Seidel, F. Stephan
Random subgroups of rationals |
| 17:30 |
Welcome Reception |
|
Tuesday, August 27th |
| 08:20 - 09:00 |
Registration & Refreshments |
| 09:00 - 10:00 |
Invited Talk:
Alexandra Silva
Guarded Kleene Algebra with Tests:
Verification of Uninterpreted Programs in Nearly Linear Time |
| 10:00 - 10:40 |
Coffee Break |
| 10:40 - 12:00 |
4A - Parameterized Algorithms I |
4B - Logic I |
|
J. Dörfler, M. Roth, J. Schmitt, P. Wellnitz
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness |
D. Figueira, V. Ramanathan, P. Weil
The Quantifier Alternation Hierarchy of Synchronous Relations |
|
S. Bessy, M. Bougeret, R. Krithika, A. Sahu, S. Saurabh, J. Thiebaut, M. Zehavi
Packing Arc-Disjoint Cycles in Tournaments |
A. Padmanabha, R. Ramanujam
Two variable fragment of Term Modal Logic |
|
J. Madathil, R. Sharma, M. Zehavi
A Sub-exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs |
E. Grädel, S. Schalthöfer
Choiceless Logarithmic Space |
| 12:00 - 14:00 |
Lunch |
| 14:00 - 15:40 |
5A - Parameterized Algorithms II |
5B - Logic II + Approximation |
|
R. Červený, O. Suchy
Faster FPT Algorithm for 5-Path Vertex Cover |
V. Lagerkvist, G. Nordh
On the Strength of Uniqueness Quantification in Primitive Positive Formulas |
|
D. Knop, T. Masařík, T. Toufar
Parameterized Complexity of Fair Vertex Evaluation Problems |
M. Garlík
Resolution Lower Bounds for Refutation Statements |
|
L. Jaffke, P. Thome de Lima
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs |
E. Fluck
Tangles and Single Linkage Hierarchical Clustering |
|
A. Agrawal, P. Jain, L. Kanesh, S. Saurabh
Parameterized Complexity of Conflict-Free Matchings and Paths |
I. Haviv
Approximating the Orthogonality Dimension of Graphs and Hypergraphs |
| 15:40 - 16:10 |
Coffee Break |
| 16:10 - 17:30 |
6A - Parameterized Algorithms III |
6B - Graphs, Groups and Words |
|
C. Einarson, F. Reidl
Domination above r-independence: Does sparseness help? |
M. Lohrey, A. Weiß
The power word problem |
|
E. Galby, P. Thome de Lima, B. Ries
Reducing the domination number of graphs via edge contractions |
J. Day, F. Manea, D. Nowotka
Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations |
|
E. Eiben, R. Ganian, T. Hamm, O. Kwon
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth |
S. Kiefer, D. Neuen
The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs |
|
Wednesday, August 28th |
| 08:20 - 09:00 |
Registration & Refreshments |
| 09:00 - 10:00 |
Invited Talk:
Daniel Lokshtanov
Picking Random Vertices |
| 10:00 - 10:40 |
Coffee Break |
| 10:40 - 12:00 |
7A - Complexity & Decidability I |
7B - Expressability |
|
N. Aubrun, S. Barbieri, E. Moutot
The Domino Problem is Undecidable on Surface Groups |
N. Galesi, D. Itsykson, A. Riazanov, A. Sofronova
Bounded-depth Frege complexity of Tseitin formulas for all graphs |
|
T. Dose
P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-pairs Relative to an Oracle |
P. Clairambault, A. Murawski
On the expressivity of linear recursion schemes |
|
M. Hoyrup, D. Stull
Semicomputable points in Euclidean spaces |
F. Koechlin, C. Nicaud, P. Rotondo
Uniform Random Expressions Lack Expressivity |
| 12:00 - 14:00 |
Lunch |
| 14:00 - 15:20 |
8A - Complexity & Decidability II |
8B - Temporal, Geometric and
Quantum Algorithms |
|
C. Ramya, R. Rao B V
Lower bounds for multilinear order-restricted ABPs |
T. Carette, D. Horsman, S. Perdrix
SZX-calculus: Scalable Graphical Quantum Reasoning |
|
N. Gupta, C. Saha
On the symmetries of and equivalence test for design polynomials |
K. Chen, A. Dumitrescu, W. Mulzer, C. Toth
On the Stretch Factor of Polygonal Chains |
|
J. Böker, Y. Chen, M. Grohe, G. Rattan
The Complexity of Homomorphism Indistinguishability |
J. Enright, K. Meeks, G. Mertzios, V. Zamaraev
Deleting edges to restrict the size of an epidemic in temporal networks |
| 15:20 - 16:15 |
Coffee Break |
| 16:15 - 22:00 |
Social Event & Conference Dinner |
|
Thursday, August 29th |
| 08:20 - 09:00 |
Registration & Refreshments |
| 09:00 - 10:00 |
Invited Talk:
Kavitha Telikepalli
Popular Matchings: Good, Bad, and Mixed |
| 10:00 - 10:40 |
Coffee Break |
| 10:40 - 12:00 |
9A - Counting and Enumeration |
9B - Automata and Formal Languages I |
|
C. Berkholz, N. Schweikardt
Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width |
N. Lhote, V. Michielini, M. Skrzypczak
Uniformisation gives the full strength of regular languages |
|
A. Bulatov, A. Kazeminia
Counting Homomorphisms Modulo a Prime Number |
W. Czerwiński, S. Lasota, C. Löding, R. Piórkowski
New Pumping Technique for 2-dimensional VASS |
|
A. Bulatov, S. Živný
Approximate counting CSP seen from the other side |
H. Fernau, V. V. Gusev, S. Hoffmann, M. Holzer, M. V. Volkov, P. Wolf
Computational Complexity of Synchronization under Regular Constraints |
| 12:00 - 14:00 |
Lunch |
| 14:00 - 15:40 |
10A - Faster Algorithms |
10B - Automata and Formal Languages II |
|
T. Hagerup
A Constant-Time Colored Choice Dictionary with Almost Robust Iteration |
A. Dennunzio, E. Formenti, D. Grinberg, L. Margara
Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties |
|
S. Baswana, S. Gupta, A. Tulsyan
Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient |
S. Bose, K. Shankara Narayanan, A. Muscholl, V. Penelle, G. Puppis
On Synthesis of Resynchronizers for Transducers |
|
R. Clifford, P. Gawrychowski, T. Kociumaka, D. Martin, P. Uznański
RLE edit distance in near optimal time |
P. Bell, M. Hirvensalo
Acceptance Ambiguity for Quantum Automata |
|
S. Chakraborty, K. Sadakane
Indexing Graph Search Trees and Applications |
P. Bille, I. Li Gørtz
From Regular Expression Matching to Parsing |
| 15:40 - 16:10 |
Coffee Break |
| 16:10 - 17:30 |
11A - Combinatorial Algorithms |
11B - Automata and Formal Languages III |
|
E. Aichinger
Solving systems of equations in supernilpotent algebras |
T. Lopez, B. Monmege, J. Talbot
Determinisation of Finitely-Ambiguous Copyless Cost Register Automata |
|
A. Conte, R. Grossi, M. Moustapha Kanté, A. Marino, T. Uno, K. Wasa
Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs |
M. Droste, P. Gastin
Aperiodic Weighted Automata and Weighted First-Order Logic |
|
S. Gaspers, R. Li
Enumeration of Preferred Extensions in Almost Oriented Digraphs |
P. Ganty, E. Gutiérrez, P. Valero
A Congruence-based Perspective on Automata Minimization Algorithms |
|
Friday, August 30th |
| 08:20 - 09:00 |
Registration & Refreshments |
| 09:00 - 10:00 |
Invited Talk:
Jérôme Leroux
Petri Net Reachability Problem |
| 10:00 - 10:40 |
Coffee Break |
| 10:40 - 12:00 |
12A - Reconfiguration problems |
12B - Matrices |
|
E. Burjons Pujol, F. Frei, E. Hemaspaandra, D. Komm, D. Wehner
Finding Optimal Solutions With Neighborly Help |
C. Carlson, K. Chandrasekaran, H. Chang, N. Kakimura, A. Kolla
Spectral Aspects of Symmetric Matrix Signings |
|
H. Mizuta, T. Hatanaka, T. Ito, X. Zhou
Reconfiguration of Minimum Steiner Trees via Vertex Exchanges |
S. Kiefer, C. Widdershoven
Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques |
|
M. Bonamy, N. Bousquet, M. Heinrich, T. Ito, Y. Kobayashi, A. Mary, M. Muehlenthaler, K. Wasa
The Perfect Matching Reconfiguration Problem |
P. Bell, I. Potapov, P. Semukhin
On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond |
| 12:00 - 14:00 |
Lunch |
| 14:00 - 19:00 |
Workshops |
|