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

Social program

March 8: Reception in the Leibnizhaus (18:30-22:00)

March 9: Excursion/guided city walk

March 10: Conference Dinner (18:00-22:00)