Click to download poster in pdf.

STACS 2019

The 36th International Symposium on Theoretical Aspects of Computer Science (STACS'19)
will be held in Berlin, Germany, March 13–16, 2019.
The conference will take place in the math building of TU Berlin.

For registration, please follow the link.

For previous editions of STACS, please see here.



Authors are invited to submit papers presenting original and unpublished research on theoretical aspects of computer science.
Typical areas include (but are not limited to):

  • algorithms and data structures, including: design of parallel, distributed, approximation, parameterized and randomized algorithms; analysis of algorithms and combinatorics of data structures; computational geometry, cryptography, algorithmic learning theory, algorithmic game theory;
  • automata and formal languages, including: algebraic and categorical methods, coding theory;
  • complexity and computability, including: computational and structural complexity theory, parameterized complexity, randomness in computation;
  • logic in computer science, including: finite model theory, database theory, semantics, specification verification, rewriting and deduction;
  • current challenges, for example: natural computing, quantum computing, mobile and net computing, computational social choice.

Paper Submission and Format

Submissions can be uploaded to EasyChair:
Authors are invited to submit a draft of a full paper with at most 12 pages (excluding the title page and the references section). The title page consists exclusively of the title of the paper, author information, and abstract.
The usage of pdflatex and the LIPIcs style file (see are mandatory; no changes to font size, page geometry, etc. are permitted. Submissions not in the correct format or submitted after the deadline will not be considered.
The paper should contain a succinct statement of the issues and of their motivation, a summary of the main results, and a brief explanation of their significance, accessible to non-specialist readers.
Proofs omitted due to space constraints must be put into a clearly marked appendix, to be read by the program committee members at their discretion.
Simultaneous submission to other conferences with published proceedings or to journals is not allowed. PC members are excluded from submitting.
There will be a rebuttal period for authors between November 26—29, 2018. Authors will receive the reviews of their submissions (via EasyChair) and have three days to submit rebuttals (via EasyChair). These rebuttals become part of the PC meeting, but entail no specific responses.


Accepted papers will be published in the proceedings of the symposium. As usual, these proceedings will appear in the Leibniz International Proceedings in Informatics (LIPIcs) series, based at Schloss Dagstuhl. This guarantees perennial, free and easy electronic access, while the authors retain the rights over their work. With their submission, authors consent to sign a license authorizing the program committee chairs to organize the electronic publication of their paper, provided the paper is accepted.

Important Dates

Deadline for submissions:
October 1, 2018 (AoE)
November 26–29, 2018
Author notification:
December 20, 2018

Final version:
January 16, 2019 (AoE)

Early registration deadline:
January 31, 2019 (AoE)

STACS 2019:
March 13–16, 2019

Invited Speakers

Leslie Ann Goldberg (Oxford):
"Computational Complexity and Partition Functions"

Anca Muscholl (Bordeaux):
"The Many Facets of String Transducers"

Petra Mutzel (Dortmund):
"Algorithmic Data Analysis"


(on March 13, 2019)

Tobias Friedrich (Potsdam):
"Network Science"

Karl Bringmann (Saarbrücken):
"Fine-Grained Complexity Theory"

Accepted Papers

Thomas Watson: A ZPP^NP[1] Lifting Theorem
Eva-Maria Hols and Stefan Kratsch: On Kernelization for Edge Dominating Set under Structural Parameters
Alexander Birx and Yann Disser: Tight analysis of the Smartstart algorithm for online Dial-a-Ride on the line
Bart M. P. Jansen, Marcin Pilipczuk and Erik Jan van Leeuwen: A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs
Max Bannach and Till Tantau: On the Descriptive Complexity of Color Coding
Antoine Mottet and Karin Quaas: The Containment Problem for Unambiguous Register Automata
Stasys Jukna and Andrzej Lingas: Lower Bounds for DeMorgan Circuits of Bounded Negation Width
Ágnes Cseh and Attila Juhos: Pairwise preferences in the stable marriage problem
Silvia Butti and Stanislav Živný: Sparsification of Binary CSPs
Gleb Posobin and Alexander Shen: Random noise increases Kolmogorov complexity and Hausdorff dimension
Boris Aronov, Omrit Filtser, Matthew Katz and Khadijeh Sheikhan: Bipartite Diameter and Other Measures Under Translation
Etienne Bamas and Louis Esperet: Distributed coloring of graphs with an optimal number of colors
Maria Emilia Descotte, Diego Figueira and Santiago Figueira: Closure properties of synchronized relations
Fedor Fomin, Petr Golovach and Dimitrios Thilikos: Modification to Planarity is Fixed Parameter Tractable
Kasper Green Larsen: Constructive Discrepancy Minimization with Hereditary L2 Guarantees
Julien Destombes and Andrei Romashchenko: Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
Erik Paul: Finite Sequentiality of Unambiguous Max-Plus Tree Automata
Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi and Florian Sikora: Token Sliding on Split Graphs
Stefan Kiefer and Corto Mascle: On Finite Monoids over Nonnegative Integer Matrices and Short Killing Words
Gregor Matl and Stanislav Živný: Beyond Boolean Surjective VCSPs
Marthe Bonamy, Oscar Defrain, Marc Heinrich and Jean-Florent Raymond: Enumerating minimal dominating sets in triangle-free graphs
Robert Krauthgamer and Ohad Trabelsi: The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern
Chetan Gupta, Vimal Raj Sharma and Raghunath Tewari: Reachability in O(log n) Genus Graphs is in Unambiguous Logspace
Derek Holt, Markus Lohrey and Saul Schleimer: Compressed decision problems in hyperbolic groups
Sandeep Sen: A unified approach to tail estimates for Randomized Inremental Construction
Alexander Grigoriev, Tim Hartmann, Stefan Lendl and Gerhard J. Woeginger: Dispersing obnoxious facilities on a graph
David Saulpic, Niklas Hjuler, Giuseppe F. Italiano and Nikos Parotsidis: Dominating Sets and Connected Dominating Sets in Dynamic Graphs
Emmanuel Jeandel and Pascal Vanier: A characterization of subshifts with a computable language
Dušan Knop, Michał Pilipczuk and Marcin Wrochna: Tight complexity lower bounds for integer linear programming with few constraints
Pál András Papp and Roger Wattenhofer: Stabilization Time in Weighted Minority Processes
Eduard Eiben, Dušan Knop, Fahad Panolan and Ondrej Suchy: Complexity of the Steiner Network Problem with Respect to the Number of Terminals
Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib and Troy Lee: Bounding quantum-classical separations for classes of nonlocal games
Felix Hommelsheim, Moritz Muehlenthaler and Oliver Schaudt: How to Secure Matchings Against Edge Failures
Shahbaz Khan and Shashank K. Mehta: Depth First Search in the Semi-streaming Model
Parinya Chalermsook, Andreas Schmid and Sumedha Uniyal: A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs
Shaull Almagor, Joel Ouaknine and James Worrell: The Semialgebraic Orbit Problem
Moses Ganardi: Visibly pushdown languages over sliding windows
Patrick Landwehr and Christof Löding: Tree Automata with Global Constraints for Infinite Trees
Spyros Angelopoulos, Christoph Dürr and Shendan Jin: Best-of-two-worlds analysis of online search
Faith Ellen, Rati Gelashvili, Philipp Woelfel and Leqi Zhu: Space Lower Bounds for the Signal Detection Problem
Yann Strozecki, David Auger and Pierre Coucheney: Solving simple stochastic games with few random nodes faster using Bland's rule
Florent Capelli and Stefan Mengel: Tractable QBF by Knowledge Compilation
Olaf Beyersdorff, Joshua Blinkhorn and Meena Mahajan: Building Strategies into QBF Proofs
François Le Gall, Harumichi Nishimura and Ansis Rosmanis: Quantum Advantage for the LOCAL Model in Distributed Computing
Martin Dietzfelbinger and Stefan Walzer: Constant-Time Retrieval with O(log m) Extra Bits
Sagnik Mukhopadhyay and Bruno Loff: Lifting Theorems for Equality
Grzegorz Fabiański, Michał Pilipczuk, Sebastian Siebertz and Szymon Toruńczyk: Progressive Algorithms for Domination and Independence
Kelin Luo, Thomas Erlebach and Yinfeng Xu: Car-Sharing on a Star Network: On-line Scheduling with $k$ Servers
Stephan Kreutzer, Irene Muzi, Patrice Ossona de Mendez, Roman Rabinovich and Sebastian Siebertz: Algorithmic Properties of Sparse Digraphs
Archontia Giannopoulou, O-Joung Kwon, Jean-Florent Raymond and Dimitrios Thilikos: Lean tree-cut decompositions: obstructions and algorithms
Pawel Gawrychowski, Florin Manea and Radoslaw Serafin: Fast and Longest Rollercoasters
Turlough Neary and Matthew Cook: Average-Case Completeness in Tag Systems
Enoch Peserico: Paging with dynamic memory capacity
Kurtulus Gemici, Elias Koutsoupias, Barnabé Monnot, Christos Papadimitriou and Georgios Piliouras: Wealth Inequality and the Price of Anarchy



Wednesday (13/03/2019):

  • 01:00 pm - 02:30 pm: Tobias Friedrich (Network Science)
  • 02:45 pm - 04:15 pm: Karl Bringmann (Fine-Grained Complexity Theory, Part I)
  • 04:30 pm - 06:00 pm: Karl Bringmann (Fine-Grained Complexity Theory, Part II)
  • around 07:00 pm: Welcome Reception

The tutorial take place in the room MA 005.
The welcome reception will take place at the Lichthof in the main building of the TU Berlin.

Thursday (14/03/2019), Friday (15/03/2019), and Saturday (16/03/2019):

(also available as pdf)


Steering Committee

Program Committee

Organizing Committee

(Contact: stacs2019 'at' akt 'dot' tu-berlin 'dot' de)

Local Guide

Arrival by train or plane

Berlins airports are Airport Schoenefeld (SXF) and Airport Tegel (TXL).

From Tegel Airport (TXL)
There are several bus lines leading into city center. The bus line X9 stops at U Ernst-Reuter-Platz.

From Schoenefeld Airport (SXF)
There are regional trains RE7 und RB14 (sometimes also called "Schoenefeld Express") operating between SXF and S+U Zoologischer Garten twice per hour (between 4 am to 11 pm). The trains stop additionally at S+U Alexanderplatz and Berlin Hauptbahnhof (main station), amongst others.
Be aware of the fact that SXF is located in the fare zone C: That said, in order to go to fare zone A (where TU Berlin is located) by public transport, you are requested to purchase an "ABC" ticket.

From Berlin Central Train Station (Hauptbahnhof, HBF)
There are several S-Bahn lines going to S Tiergarten or S+U Zoologischer Garten. If you plan to come by train you may consider to use the provided gadget.

Getting around TU Berlin campus

Closest stations to math building of TU Berlin:

  • U-Bhf Ernst-Reuter-Platz (Metro station: line U2; Bus station: lines X9, 245, M45)
  • Marchstraße (Bus station: lines 245, M45)
Larger stations in 10-20 min walking distance to math building of TU Berlin:
  • S+U Zoologischer Garten
    (Regional trains; Metro: lines U2, U9; S-Bahn: lines S3, S5, S7, S9, S75; Bus: lines X9, X10, M45, M46, M49, 100, 109, 110, 200)
  • S-Bhf Tiergarten
    (S-Bahn: lines S3, S5, S7, S9, S75)
  • U-Bhf Bismarcksraße
    (Metro: lines U7, U2)

Lunch options on and around TU Berlin campus

The TU Berlin offers several lunch options.
At all of the following lunch options at TU campus, at least one vegetarian dish is usually offered.
TU Berlin has a Mensa (usually also offers a vegan dish) and a canteen:

And a couple of so-called cafeterias and cafés: In addition, there are plenty of restaurants around TU Berlin, for example at (and on the way from TU Berlin to) Savignyplatz.

Sponsored by

DFG and TU Berlin