STACS 2019 March 13-16, 2019, Berlin, Germany

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)



Rolf Niedermeier and Christophe Paul (Eds.)
ISBN 978-3-95977-100-9, LIPICS Vol. 126 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 32 MB)
Search Publication Server

Authors
  • Almagor, Shaull
  • Angelopoulos, Spyros
  • Aronov, Boris
  • Auger, David
  • Bamas, Étienne
  • Bannach, Max
  • Bannink, Tom
  • Belmonte, Rémy
  • Beyersdorff, Olaf
  • Birx, Alexander
  • Blinkhorn, Joshua
  • Bonamy, Marthe
  • Briët, Jop
  • Bringmann, Karl
  • Buhrman, Harry
  • Butti, Silvia
  • Capelli, Florent
  • Chalermsook, Parinya
  • Cook, Matthew
  • Coucheney, Pierre
  • Cseh, Ágnes
  • Defrain, Oscar
  • Descotte, María Emilia
  • Destombes, Julien
  • Dietzfelbinger, Martin
  • Disser, Yann
  • Dürr, Christoph
  • Eiben, Eduard
  • Ellen, Faith
  • Erlebach, Thomas
  • Esperet, Louis
  • Fabianski, Grzegorz
  • Figueira, Diego
  • Figueira, Santiago
  • Filtser, Omrit
  • Fomin, Fedor V.
  • Friedrich, Tobias
  • Ganardi, Moses
  • Gawrychowski, Pawel
  • Gelashvili, Rati
  • Gemici, Kurtulus
  • Giannopoulou, Archontia C.
  • Goldberg, Leslie Ann
  • Golovach, Petr A.
  • Grigoriev, Alexander
  • Gupta, Chetan
  • Hartmann, Tim A.
  • Heinrich, Marc
  • Hjuler, Niklas
  • Hols, Eva-Maria C.
  • Holt, Derek
  • Hommelsheim, Felix
  • Italiano, Giuseppe F.
  • Jansen, Bart M. P.
  • Jeandel, Emmanuel
  • Jin, Shendan
  • Juhos, Attila
  • Jukna, Stasys
  • Katz, Matthew J.
  • Khan, Shahbaz
  • Kiefer, Stefan
  • Kim, Eun Jung
  • K. Mehta, Shashank
  • Knop, Dusan
  • Koutsoupias, Elias
  • Kratsch, Stefan
  • Krauthgamer, Robert
  • Kreutzer, Stephan
  • Kwon, O-joung
  • Labib, Farrokh
  • Lampis, Michael
  • Landwehr, Patrick
  • Larsen, Kasper Green
  • Lee, Troy
  • Le Gall, François
  • Lendl, Stefan
  • Lingas, Andrzej
  • Löding, Christof
  • Loff, Bruno
  • Lohrey, Markus
  • Luo, Kelin
  • Mahajan, Meena
  • Manea, Florin
  • Mascle, Corto
  • Matl, Gregor
  • Mengel, Stefan
  • Mitsou, Valia
  • Monnot, Barnabé
  • Mottet, Antoine
  • Mühlenthaler, Moritz
  • Mukhopadhyay, Sagnik
  • Muscholl, Anca
  • Mutzel, Petra
  • Muzi, Irene
  • Neary, Turlough
  • Niedermeier, Rolf
  • Nishimura, Harumichi
  • Ossona de Mendez, Patrice
  • Otachi, Yota
  • Ouaknine, Joël
  • Panolan, Fahad
  • Papadimitriou, Christos H.
  • Papp, Pál András
  • Parotsidis, Nikos
  • Paul, Christophe
  • Paul, Erik
  • Peserico, Enoch
  • Piliouras, Georgios
  • Pilipczuk, Marcin
  • Pilipczuk, Michal
  • Posobin, Gleb
  • Puppis, Gabriele
  • Quaas, Karin
  • Rabinovich, Roman
  • Raymond, Jean-Florent
  • Romashchenko, Andrei
  • Rosmanis, Ansis
  • Saulpic, David
  • Schaudt, Oliver
  • Schleimer, Saul
  • Schmid, Andreas
  • Sen, Sandeep
  • Serafin, Radoslaw
  • Sharma, Vimal Raj
  • Sheikhan, Khadijeh
  • Shen, Alexander
  • Siebertz, Sebastian
  • Sikora, Florian
  • Strozecki, Yann
  • Suchý, Ondrej
  • Tantau, Till
  • Tewari, Raghunath
  • Thilikos, Dimitrios M.
  • Torunczyk, Szymon
  • Trabelsi, Ohad
  • Uniyal, Sumedha
  • Vanier, Pascal
  • van Leeuwen, Erik Jan
  • Walzer, Stefan
  • Watson, Thomas
  • Wattenhofer, Roger
  • Woeginger, Gerhard J.
  • Woelfel, Philipp
  • Worrell, James
  • Wrochna, Marcin
  • Xu, Yinfeng
  • Zhu, Leqi
  • Zivný, Stanislav
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Niedermeier, Rolf ; Paul, Christophe

    Abstract | Document (348 KB) | BibTeX

    Computational Complexity and Partition Functions (Invited Talk)
    Authors: Goldberg, Leslie Ann

    Abstract | Document (295 KB) | BibTeX

    The Many Facets of String Transducers (Invited Talk)
    Authors: Muscholl, Anca ; Puppis, Gabriele

    Abstract | Document (573 KB) | BibTeX

    Algorithmic Data Science (Invited Talk)
    Authors: Mutzel, Petra

    Abstract | Document (1,047 KB) | BibTeX

    Fine-Grained Complexity Theory (Tutorial)
    Authors: Bringmann, Karl

    Abstract | Document (393 KB) | BibTeX

    From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
    Authors: Friedrich, Tobias

    Abstract | Document (3,258 KB) | BibTeX

    The Semialgebraic Orbit Problem
    Authors: Almagor, Shaull ; Ouaknine, Joël ; Worrell, James

    Abstract | Document (531 KB) | BibTeX

    Best-Of-Two-Worlds Analysis of Online Search
    Authors: Angelopoulos, Spyros ; Dürr, Christoph ; Jin, Shendan

    Abstract | Document (492 KB) | BibTeX

    Bipartite Diameter and Other Measures Under Translation
    Authors: Aronov, Boris ; Filtser, Omrit ; Katz, Matthew J. ; Sheikhan, Khadijeh

    Abstract | Document (486 KB) | BibTeX

    Solving Simple Stochastic Games with Few Random Nodes Faster Using Bland's Rule
    Authors: Auger, David ; Coucheney, Pierre ; Strozecki, Yann

    Abstract | Document (534 KB) | BibTeX

    Distributed Coloring of Graphs with an Optimal Number of Colors
    Authors: Bamas, Étienne ; Esperet, Louis

    Abstract | Document (540 KB) | BibTeX

    On the Descriptive Complexity of Color Coding
    Authors: Bannach, Max ; Tantau, Till

    Abstract | Document (513 KB) | BibTeX

    Bounding Quantum-Classical Separations for Classes of Nonlocal Games
    Authors: Bannink, Tom ; Briët, Jop ; Buhrman, Harry ; Labib, Farrokh ; Lee, Troy

    Abstract | Document (474 KB) | BibTeX

    Token Sliding on Split Graphs
    Authors: Belmonte, Rémy ; Kim, Eun Jung ; Lampis, Michael ; Mitsou, Valia ; Otachi, Yota ; Sikora, Florian

    Abstract | Document (503 KB) | BibTeX

    Building Strategies into QBF Proofs
    Authors: Beyersdorff, Olaf ; Blinkhorn, Joshua ; Mahajan, Meena

    Abstract | Document (566 KB) | BibTeX

    Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line
    Authors: Birx, Alexander ; Disser, Yann

    Abstract | Document (515 KB) | BibTeX

    Enumerating Minimal Dominating Sets in Triangle-Free Graphs
    Authors: Bonamy, Marthe ; Defrain, Oscar ; Heinrich, Marc ; Raymond, Jean-Florent

    Abstract | Document (532 KB) | BibTeX

    Sparsification of Binary CSPs
    Authors: Butti, Silvia ; Zivný, Stanislav

    Abstract | Document (427 KB) | BibTeX

    Tractable QBF by Knowledge Compilation
    Authors: Capelli, Florent ; Mengel, Stefan

    Abstract | Document (586 KB) | BibTeX

    A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs
    Authors: Chalermsook, Parinya ; Schmid, Andreas ; Uniyal, Sumedha

    Abstract | Document (726 KB) | BibTeX

    Average-Case Completeness in Tag Systems
    Authors: Cook, Matthew ; Neary, Turlough

    Abstract | Document (507 KB) | BibTeX

    Pairwise Preferences in the Stable Marriage Problem
    Authors: Cseh, Ágnes ; Juhos, Attila

    Abstract | Document (469 KB) | BibTeX

    Closure Properties of Synchronized Relations
    Authors: Descotte, María Emilia ; Figueira, Diego ; Figueira, Santiago

    Abstract | Document (561 KB) | BibTeX

    Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
    Authors: Destombes, Julien ; Romashchenko, Andrei

    Abstract | Document (535 KB) | BibTeX

    Constant-Time Retrieval with O(log m) Extra Bits
    Authors: Dietzfelbinger, Martin ; Walzer, Stefan

    Abstract | Document (690 KB) | BibTeX

    Complexity of the Steiner Network Problem with Respect to the Number of Terminals
    Authors: Eiben, Eduard ; Knop, Dusan ; Panolan, Fahad ; Suchý, Ondrej

    Abstract | Document (593 KB) | BibTeX

    Space Lower Bounds for the Signal Detection Problem
    Authors: Ellen, Faith ; Gelashvili, Rati ; Woelfel, Philipp ; Zhu, Leqi

    Abstract | Document (483 KB) | BibTeX

    Progressive Algorithms for Domination and Independence
    Authors: Fabianski, Grzegorz ; Pilipczuk, Michal ; Siebertz, Sebastian ; Torunczyk, Szymon

    Abstract | Document (864 KB) | BibTeX

    Modification to Planarity is Fixed Parameter Tractable
    Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Thilikos, Dimitrios M.

    Abstract | Document (844 KB) | BibTeX

    Visibly Pushdown Languages over Sliding Windows
    Authors: Ganardi, Moses

    Abstract | Document (555 KB) | BibTeX

    Fast and Longest Rollercoasters
    Authors: Gawrychowski, Pawel ; Manea, Florin ; Serafin, Radoslaw

    Abstract | Document (692 KB) | BibTeX

    Wealth Inequality and the Price of Anarchy
    Authors: Gemici, Kurtulus ; Koutsoupias, Elias ; Monnot, Barnabé ; Papadimitriou, Christos H. ; Piliouras, Georgios

    Abstract | Document (544 KB) | BibTeX

    Lean Tree-Cut Decompositions: Obstructions and Algorithms
    Authors: Giannopoulou, Archontia C. ; Kwon, O-joung ; Raymond, Jean-Florent ; Thilikos, Dimitrios M.

    Abstract | Document (650 KB) | BibTeX

    Dispersing Obnoxious Facilities on a Graph
    Authors: Grigoriev, Alexander ; Hartmann, Tim A. ; Lendl, Stefan ; Woeginger, Gerhard J.

    Abstract | Document (448 KB) | BibTeX

    Reachability in O(log n) Genus Graphs is in Unambiguous Logspace
    Authors: Gupta, Chetan ; Sharma, Vimal Raj ; Tewari, Raghunath

    Abstract | Document (540 KB) | BibTeX

    Dominating Sets and Connected Dominating Sets in Dynamic Graphs
    Authors: Hjuler, Niklas ; Italiano, Giuseppe F. ; Parotsidis, Nikos ; Saulpic, David

    Abstract | Document (506 KB) | BibTeX

    On Kernelization for Edge Dominating Set under Structural Parameters
    Authors: Hols, Eva-Maria C. ; Kratsch, Stefan

    Abstract | Document (572 KB) | BibTeX

    Compressed Decision Problems in Hyperbolic Groups
    Authors: Holt, Derek ; Lohrey, Markus ; Schleimer, Saul

    Abstract | Document (496 KB) | BibTeX

    How to Secure Matchings Against Edge Failures
    Authors: Hommelsheim, Felix ; Mühlenthaler, Moritz ; Schaudt, Oliver

    Abstract | Document (533 KB) | BibTeX

    A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
    Authors: Jansen, Bart M. P. ; Pilipczuk, Marcin ; van Leeuwen, Erik Jan

    Abstract | Document (598 KB) | BibTeX

    A Characterization of Subshifts with Computable Language
    Authors: Jeandel, Emmanuel ; Vanier, Pascal

    Abstract | Document (667 KB) | BibTeX

    Lower Bounds for DeMorgan Circuits of Bounded Negation Width
    Authors: Jukna, Stasys ; Lingas, Andrzej

    Abstract | Document (497 KB) | BibTeX

    Depth First Search in the Semi-streaming Model
    Authors: Khan, Shahbaz ; K. Mehta, Shashank

    Abstract | Document (512 KB) | BibTeX

    On Finite Monoids over Nonnegative Integer Matrices and Short Killing Words
    Authors: Kiefer, Stefan ; Mascle, Corto

    Abstract | Document (478 KB) | BibTeX

    Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints
    Authors: Knop, Dusan ; Pilipczuk, Michal ; Wrochna, Marcin

    Abstract | Document (777 KB) | BibTeX

    The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern
    Authors: Krauthgamer, Robert ; Trabelsi, Ohad

    Abstract | Document (774 KB) | BibTeX

    Algorithmic Properties of Sparse Digraphs
    Authors: Kreutzer, Stephan ; Muzi, Irene ; Ossona de Mendez, Patrice ; Rabinovich, Roman ; Siebertz, Sebastian

    Abstract | Document (867 KB) | BibTeX

    Tree Automata with Global Constraints for Infinite Trees
    Authors: Landwehr, Patrick ; Löding, Christof

    Abstract | Document (481 KB) | BibTeX

    Constructive Discrepancy Minimization with Hereditary L2 Guarantees
    Authors: Larsen, Kasper Green

    Abstract | Document (551 KB) | BibTeX

    Quantum Advantage for the LOCAL Model in Distributed Computing
    Authors: Le Gall, François ; Nishimura, Harumichi ; Rosmanis, Ansis

    Abstract | Document (500 KB) | BibTeX

    Lifting Theorems for Equality
    Authors: Loff, Bruno ; Mukhopadhyay, Sagnik

    Abstract | Document (617 KB) | BibTeX

    Car-Sharing on a Star Network: On-Line Scheduling with k Servers
    Authors: Luo, Kelin ; Erlebach, Thomas ; Xu, Yinfeng

    Abstract | Document (554 KB) | BibTeX

    Beyond Boolean Surjective VCSPs
    Authors: Matl, Gregor ; Zivný, Stanislav

    Abstract | Document (560 KB) | BibTeX

    The Containment Problem for Unambiguous Register Automata
    Authors: Mottet, Antoine ; Quaas, Karin

    Abstract | Document (572 KB) | BibTeX

    Stabilization Time in Weighted Minority Processes
    Authors: Papp, Pál András ; Wattenhofer, Roger

    Abstract | Document (492 KB) | BibTeX

    Finite Sequentiality of Unambiguous Max-Plus Tree Automata
    Authors: Paul, Erik

    Abstract | Document (512 KB) | BibTeX

    Paging with Dynamic Memory Capacity
    Authors: Peserico, Enoch

    Abstract | Document (522 KB) | BibTeX

    Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension
    Authors: Posobin, Gleb ; Shen, Alexander

    Abstract | Document (504 KB) | BibTeX

    A Unified Approach to Tail Estimates for Randomized Incremental Construction
    Authors: Sen, Sandeep

    Abstract | Document (729 KB) | BibTeX

    A ZPP^NP[1] Lifting Theorem
    Authors: Watson, Thomas

    Abstract | Document (614 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI