Program
Satellite workshops
AlMoTh 2017 will take place as a STACS satellite workshop at March 7-8.
Conference Guide:
The conference guide (including the program) is now available for download: <link typo3 stacs-guide.pdf>Download (PDF)
Scientific program
Wednesday, March 8
Tutorial Session (14:00–17:00)
chair: Heribert Vollmer
| 14:00–17:00 | Juha Kontinen: |
|---|---|
| (15:15 break) | Computational Aspects of Logics in Team Semantics |
Thursday, March 9
Invited Talk (09:00–10:00)
chair: Brigitte Vallée
| 09:00–10:00 | Antoine Joux: |
|---|---|
| Discrete logarithms in small characteristic finite fields: A survey of recent advances |
Session A (10:20–11:35)
chair: Till Tantau
| 10:20 | Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert and Jacobo Torán: |
|---|---|
| Parameterized complexity of small weight automorphisms |
| 10:45 | Stanislav Böhm, Stefan Göller, Simon Halfon and Piotr Hofman : |
|---|---|
| On Büchi one-counter automata |
| 11:10 | Mikołaj Bojańczyk and Michał Pilipczuk: |
|---|---|
| Optimizing tree decompositions in MSO |
Session B (10:20–11:35)
chair: Artur Jeż
| 10:20 | Markus Lohrey and Georg Zetzsche: |
|---|---|
| The Complexity of Knapsack in Graph Groups |
| 10:45 | Tillmann Miltzow, Édouard Bonnet and Paweł Rzążewski: |
|---|---|
| Complexity of Token Swapping and its Variants |
| 11:10 | Jack H. Lutz and Neil Lutz: |
|---|---|
| Algorithmic information, plane Kakeya sets, and conditional dimension |
Session A (11:50–12:40)
chair: Henning Fernau
| 11:50 | Piotr Sankowski and Karol Węgrzycki: |
|---|---|
| Improved Distance Queries and Cycle Counting by Frobenius Normal Form |
| 12:15 | Lin Chen, Dániel Marx, Deshi Ye and Guochuan Zhang: |
|---|---|
| Parameterized and approximation results for scheduling with a low rank processing time matrix |
Session B (11:50–12:40)
chair: Florin Manea
| 11:50 | Juha Kärkkäinen, Dominik Kempa, Yuto Nakashima, Simon Puglisi and Arseny Shur: |
|---|---|
| On the Size of Lempel-Ziv and Lyndon Factorizations |
| 12:15 | Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth and Yannik Stein: |
|---|---|
| Improved Time-Space Trade-offs for Computing Voronoi Diagrams |
Session A (14:40–15:55)
chair: Dietrich Kuske
| 14:40 | Moses Ganardi, Markus Lohrey, Danny Hucke and Daniel König: |
|---|---|
| Circuit Evaluation for Finite Semirings |
| 15:05 | Stephane Le Roux, Arno Pauly and Jean-Francois Raskin: |
|---|---|
| Minkowski games |
| 15:30 | Gaétan Richard: |
|---|---|
| On the synchronisation problem over cellular automata |
Session B (14:40–15:55)
chair: Rolf Niedermeier
| 14:40 | Qian Li and Xiaoming Sun: |
|---|---|
| On the Sensitivity Complexity of k-Uniform Hypergraph Properties |
| 15:05 | Bernd Finkbeiner and Martin Zimmermann: |
|---|---|
| The First-Order Logic of Hyperproperties |
| 15:30 | Marianne Akian, Stephane Gaubert, Julien Grand-Clement and Jeremie Guillaud: |
|---|---|
| The operator approach to entropy games |
Session A (16:15–17:30)
chair: Jacobo Torán
| 16:15 | Dmitry Chistikov, Szabolcs Ivan, Anna Lubiw and Jeffrey Shallit: |
|---|---|
| Fractional coverings, greedy coverings, and rectifier networks |
| 16:40 | Abhishek Bhrushundi, Prahladh Harsha and Srikanth Srinivasan: |
|---|---|
| On polynomial approximations over Z/2^kZ |
| 17:05 | Zdenek Dvorak, Daniel Kral and Bojan Mohar: |
|---|---|
| Graphic TSP in cubic graphs |
Session B (16:15–17:30)
chair: Antoine Joux
| 16:15 | Yann Disser and Stefan Kratsch: |
|---|---|
| Robust and adaptive search |
| 16:40 | Lorenzo Clemente, Wojciech Czerwiński, Sławomir Lasota and Charles Paperman: |
|---|---|
| Separability of Reachability Sets of Vector Addition Systems |
| 17:05 | Samuel J. V. Gool and Benjamin Steinberg: |
|---|---|
| Pro-aperiodic monoids via saturated models |
Friday, March 10
Invited Talk (09:00–10:00)
chair: Heribert Vollmer
| 09:00–10:00 | Artur Jeż: |
|---|---|
| Recompression: new approach to word equations and context unification. |
Session A (10:20–11:35)
chair: Rüdiger Reischuk
| 10:20 | Fedor Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh and Meirav Zehavi: |
|---|---|
| Matrix Rigidity from the Viewpoint of Parameterized Complexity |
| 10:45 | Eldar Fischer, Oded Lachish and Yadu Vasudev: |
|---|---|
| Improving and extending the testing of distributions for shape-restricted properties |
| 11:10 | Zdenek Dvorak and Bernard Lidicky: |
|---|---|
| Independent sets near the lower bound in bounded degree graphs |
Session B (10:20–11:35)
chair: Markus Lohrey
| 10:20 | Suman Kalyan Bera and Amit Chakrabarti: |
|---|---|
| Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams |
| 10:45 | Shahrzad Haddadan and Peter Winkler: |
|---|---|
| Mixing of Permutations by Biased Transposition |
| 11:10 | Michael Kompatscher and Trung Van Pham: |
|---|---|
| A complexity dichotomy for poset constraint satisfaction |
Session A (11:50–12:40)
chair: Jack Lutz
| 11:50 | Titouan Carette, Mathieu Lauriere and Frederic Magniez: |
|---|---|
| Extended Learning Graphs for Triangle Finding |
| 12:15 | Petr Gregor and Torsten Mütze: |
|---|---|
| Trimming and gluing Gray codes |
Session B (11:50–12:40)
chair: Juha Kontinen
| 11:50 | Alexander Kulikov and Vladimir Podolskii: |
|---|---|
| Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates |
| 12:15 | Vittorio Bilò and Marios Mavronicolas: |
|---|---|
| ∃ℝ-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games |
Session A (14:40–15:55)
chair: Andreas Krebs
| 14:40 | Benjamin Burton, Sergio Cabello, Stefan Kratsch and William Pettersson: |
|---|---|
| The parameterized complexity of finding a 2-sphere in a simplicial complex |
| 15:05 | Vasco Brattka, Rupert Hölzl and Rutger Kuyper: |
|---|---|
| Monte Carlo Computability |
| 15:30 | Dominik D. Freydenberger and Markus L. Schmid: |
|---|---|
| Deterministic Regular Expressions With Back-References |
Session B (14:40–15:55)
chair: Olaf Beyersdorff
| 14:40 | Maciej Skorski: |
|---|---|
| Lower Bounds on Key Derivation for Square-Friendly Applications |
| 15:05 | Arkadev Chattopadhyay, Pavel Dvorak, Michal Koucky, Bruno Loff and Sagnik Mukhopadhyay: |
|---|---|
| Lower Bounds for Elimination via Weak Regularity |
| 15:30 | Robert Ganian, Ramanujan M. S. and Stefan Szeider: |
|---|---|
| Combining Treewidth and Backdoors for CSP |
Session A (16:15–17:30)
chair: Arne Meier
| 16:15 | Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz and Grischa Weberstädt: |
|---|---|
| Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs |
| 16:40 | Martin Koutecky, Dušan Knop and Matthias Mnich: |
|---|---|
| Voting and Bribing in Single-Exponential Time |
| 17:05 | Arnaud Carayol and Stefan Göller: |
|---|---|
| On long words avoiding Zimin patterns |
Session B (16:15–17:30)
chair: Christophe Paul
| 16:15 | Paul Gallot, Anca Muscholl, Gabriele Puppis and Sylvain Salvati: |
|---|---|
| On the decomposition of finite-valued streaming string transducers |
| 16:40 | Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud and Dennis Olivetti: |
|---|---|
| Local Distributed Verification |
| 17:05 | Marius Zimand: |
|---|---|
| List approximation for increasing Kolmogorov complexity |
Saturday, March 11
Invited Talk (09:00–10:00)
chair: Arne Meier
| 09:00–10:00 | Till Tantau: |
|---|---|
| Applications of Algorithmic Metatheorems to Space Complexity and Parallelism |
Session A (10:20–11:35)
chair: Henning Fernau
| 10:20 | Aleksi Saarela: |
|---|---|
| Word equations where a power equals a product of powers |
| 10:45 | Andrej Ivaskovic, Adrian Kosowski, Dominik Pajak and Thomas Sauerwald: |
|---|---|
| Multiple Random Walks on Paths and Grids |
| 11:10 | Alexander Knop, Dmitry Itsykson, Dmitry Sokolov and Andrei Romashchenko: |
|---|---|
| On OBDD based algorithms and proof systems that dynamically change order of variables |
Session B (10:20–11:35)
chair: Stefan Göller
| 10:20 | Peter Høyer and Mojtaba Komeili: |
|---|---|
| Efficient quantum walk on the grid with multiple marked elements |
| 10:45 | Nathanaël Fijalkow, Pierre Ohlmann, Joël Ouaknine, Amaury Pouly and James Worrell: |
|---|---|
| Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem |
| 11:10 | Pascal Koiran, Ignacio Garcia-Marco, Timothée Pecatte and Stéphan Thomassé: |
|---|---|
| On the complexity of partial derivatives |
Session A (11:50–12:40)
chair: Martin Dietzfelbinger
| 11:50 | Radu Curticapean, Holger Dell and Marc Roth: |
|---|---|
| Counting edge-injective homomorphisms and matchings on restricted graph classes |
| 12:15 | Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi: |
|---|---|
| Split Contraction: The Untold Story |
Session B (11:50–12:40)
chair: Christoph Dürr
| 11:50 | Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Daniel Graf, Jan Hackfeld and Paolo Penna: |
|---|---|
| Energy-efficient Delivery by Heterogenous Mobile Agents |
| 12:15 | Mohit Garg and Jaikumar Radhakrishnan: |
|---|---|
| Set membership with non-adaptive bit probes |
