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
(11:00-12:15) |
|
|
|
| 12:00-13:30 |
Lunch |
|
|
Invited Talk:
Mikołaj Bojańczyk
(13:15-14:15) |
| 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)
9:15-10:30
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?
13:30-14:45
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 |
| |
15:15-16:30
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 |
| |
16:50-18:05
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)
9:15-10: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 abelian-2-avoidable |
| Matthieu Rosenfeld |
| |
11:00-12:00: Invited Talk by Tobias Friedrich
Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms
13:30-14: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 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 |
| |
15:15-16: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. | 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 |
| |
16:50-18: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 (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)
9:15-10:30
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)
9:15-10: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:00-12:00: Invited Talk by Patricia Bouyer-Decitre
Optimal Reachability in Weighted Timed Automata and Games
13:30-14: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 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 |
| |
15:15-16:30
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 |
| |
16:50-18:05
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)
11:00-12: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 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
|