• • The information sheets accompanying the conference are available online.
  • • The STACS 2019 proceedings are available online.

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 previous editions of STACS, please see here.

Submissions

Scope

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: https://easychair.org/conferences/?conf=stacs2019.
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 http://www.dagstuhl.de/en/publications/lipics) 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.

Proceedings

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)
Rebuttal:
November 26–29, 2018
Author notification:
December 20, 2018

Final version:
January 16, 2019 (AoE)

Early registration deadline:
February 5, 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"

Tutorials

(on March 13, 2019)

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

Tobias Friedrich (Potsdam):
"Network Science"

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
Niklas Hjuler, Giuseppe F. Italiano, Nikos Parotsidis and David Saulpic: 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
David Auger, Pierre Coucheney and Yann Strozecki: 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
Bruno Loff and Sagnik Mukhopadhyay: 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
Matthew Cook and Turlough Neary: 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

Schedule

(Preliminary)

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 (until 09:00 pm)

The tutorials 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):

There will be a group photo (voluntary) on Thursday (14/03/2019), in between 12:45 pm and 01:00 pm.
On Friday (15/03/2019) evening, the social program takes place at the Aquarium Berlin (Budapester Str. 32, 10787 Berlin). There is a guided tour from 06:30 pm to 07:30 pm, and the conference dinner from 07:30 pm to 10:30 pm.

(also available as download: one page and one page per day)

Committees

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. Note that no train, metro, or tram operates from and to Tegel airport directly.

From Schoenefeld Airport (SXF)
The S-Bahn (S9, S45) operates from Schoenefeld Airport (SXF) to the city center. The S9 stops at Berlin Hauptbahnhof (main station), S+U Friedrichstraße, S Tiergarten, and S+U Zoologischer Garten (the latter two are in walking distance to the conference site).
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

On and around TU Berlin there are several lunch options.
On the TU Berlin campus, you can find several mensas, canteens, and cafés. However, note that at some places, you are only able to pay using a so-called MensaCard (in the map, indicated by blueish icons). At all of our listed lunch options around TU campus, at least one vegetarian dish is usually offered.
Lunch options with only MensaCard-payment (blueish icons):

Lunch options with cash-payment (green icons): In addition, there are plenty of restaurants around TU Berlin, for example at (and on the way from TU Berlin to) Savignyplatz. A small selection of cuisines close to TU campus is the following: Indian Cuisine, Italian Cuisine, Chinese Cuisine, Croatian Cuisine, Traditional Cuisine, (Vegetarian) Döner


Accommodation

Berlin offers many options for accommodation (like hotels, hostels, etc.). Also around the TU Berlin, there are several options. Some randomly selected hotels in walking distance to the TU Berlin are: Moreover, around the Zoo and Savignyplatz there are many options, which are still in a walking distance of 20 minutes.

Thursday: A Free Evening

Berlin is a living city, throughout the day and evening. Each district of Berlin has its own character and charme. Charlottenburg, the district where TU Berlin is located in, is home for a high variety of things to do in the evening: Schaubühne* (theater), Wühlmäuse* (cabaret), Deutsche Oper* (opera), cinemas* (four from the Yorck kino group, usually displaying movies in original language; or the Zoopalast), or simply drink and eat (see right-hand side map).

Further theatres are, for instance, the Deutsches Theater* or the Berliner Esemble*. In case you like classical music: Berliner Philharmonie*.

There is, as in every larger city, a high number of restaurants and bars worth to visit. On the right-hand side map, you find a small collection of options, several close to TU Berlin, some slightly further away (you possibly need to zoom out).

* Be aware of the fact that in case, you may need to order/reserve tickets in advance.

Sponsored by

DFG and TU Berlin