STACS 2017 March 8-11, 2017 - Hannover, Germany

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)



Heribert Vollmer and Brigitte Vallée (Eds.)
ISBN 978-3-95977-028-6, LIPICS Vol. 66 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 27 MB)
Search Publication Server

Authors
  • Agrawal, Akanksha
  • Akian, Marianne
  • Arvind, Vikraman
  • Balliu, Alkida
  • Banyassady, Bahareh
  • Bera, Suman K.
  • Bhrushundi, Abhishek
  • Bilò, Vittorio
  • Bojanczyk, Mikolaj
  • Bonnet, Édouard
  • Brattka, Vasco
  • Burton, Benjamin
  • Bärtschi, Andreas
  • Böhm, Stanislav
  • Cabello, Sergio
  • Carayol, Arnaud
  • Carette, Titouan
  • Chakrabarti, Amit
  • Chalopin, Jérémie
  • Chattopadhyay, Arkadev
  • Chen, Lin
  • Chistikov, Dmitry
  • Clemente, Lorenzo
  • Curticapean, Radu
  • Czerwinski, Wojciech
  • D'Angelo, Gianlorenzo
  • Das, Shantanu
  • Dell, Holger
  • Disser, Yann
  • Dvorák, Pavel
  • Dvorák, Zdenek
  • Fijalkow, Nathanaël
  • Finkbeiner, Bernd
  • Fischer, Eldar
  • Fomin, Fedor V.
  • Fraigniaud, Pierre
  • Freydenberger, Dominik D.
  • Gallot, Paul
  • Ganardi, Moses
  • Ganian, Robert
  • Garcia-Marco, Ignacio
  • Garg, Mohit
  • Gaubert, Stéphane
  • Graf, Daniel
  • Grand-Clément, Julien
  • Gregor, Petr
  • Guillaud, Jérémie
  • Göller, Stefan
  • Hackfeld, Jan
  • Haddadan, Shahrzad
  • Halfon, Simon
  • Harsha, Prahladh
  • Hofman, Piotr
  • Hoyer, Peter
  • Hucke, Danny
  • Hölzl, Rupert
  • Itsykson, Dmitry
  • Ivaskovic, Andrej
  • Iván, Szabolcs
  • Jez, Artur
  • Joux, Antoine
  • Kempa, Dominik
  • Knop, Alexander
  • Knop, Dusan
  • Koiran, Pascal
  • Komeili, Mojtaba
  • Kompatscher, Michael
  • Kontinen, Juha
  • Korman, Matias
  • Kosowski, Adrian
  • Koucký, Michal
  • Koutecký, Martin
  • Kratsch, Stefan
  • Kreutzer, Stephan
  • Král, Daniel
  • Kuhnert, Sebastian
  • Kulikov, Alexander S.
  • Kuyper, Rutger
  • Kärkkäinen, Juha
  • Köbler, Johannes
  • König, Daniel
  • Lachish, Oded
  • Lasota, Slawomir
  • Laurière, Mathieu
  • Le Roux, Stéphane
  • Li, Qian
  • Lidický, Bernard
  • Loff, Bruno
  • Lohrey, Markus
  • Lokshtanov, Daniel
  • Lubiw, Anna
  • Lutz, Jack H.
  • Lutz, Neil
  • Magniez, Frédéric
  • Marx, Dániel
  • Mavronicolas, Marios
  • Meesum, S. M.
  • Miltzow, Tillmann
  • Mnich, Matthias
  • Mohar, Bojan
  • Mukhopadhyay, Sagnik
  • Mulzer, Wolfgang
  • Muscholl, Anca
  • Mütze, Torsten
  • Nakashima, Yuto
  • Ohlmann, Pierre
  • Olivetti, Dennis
  • Ouaknine, Joël
  • Pajak, Dominik
  • Paperman, Charles
  • Pauly, Arno
  • Pecatte, Timothée
  • Penna, Paolo
  • Pettersson, William
  • Pham, Trung Van
  • Pilipczuk, Michal
  • Podolskii, Vladimir V.
  • Pouly, Amaury
  • Puglisi, Simon J.
  • Puppis, Gabriele
  • Rabinovich, Roman
  • Radhakrishnan, Jaikumar
  • Ramanujan, M. S.
  • Raskin, Jean-François
  • Richard, Gaétan
  • Roeloffzen, Marcel
  • Romashchenko, Andrey
  • Roth, Marc
  • Rzazewski, Pawel
  • Saarela, Aleksi
  • Salvati, Sylvain
  • Sankowski, Piotr
  • Sauerwald, Thomas
  • Saurabh, Saket
  • Schmid, Markus L.
  • Seiferth, Paul
  • Shallit, Jeffrey
  • Shur, Arseny M.
  • Siebertz, Sebastian
  • Skorski, Maciej
  • Sokolov, Dmitry
  • Srinivasan, Srikanth
  • Stein, Yannik
  • Steinberg, Benjamin
  • Sun, Xiaoming
  • Szeider, Stefan
  • Tantau, Till
  • Thomassé, Stéphan
  • Torán, Jacobo
  • Vallée, Brigitte
  • van Gool, Samuel J.
  • van Renssen, André
  • Vasudev, Yadu
  • Vollmer, Heribert
  • Weberstädt, Grischa
  • Wegrzycki, Karol
  • Winkler, Peter
  • Worrell, James
  • Ye, Deshi
  • Zehavi, Meirav
  • Zetzsche, Georg
  • Zhang, Guochuan
  • Zimand, Marius
  • Zimmermann, Martin
    		•

    		  
    Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers
    Authors: Vollmer, Heribert ; Vallée, Brigitte

    Abstract | Document (514 KB) | BibTeX

    Computational Aspects of Logics in Team Semantics (Tutorial)
    Authors: Kontinen, Juha

    Abstract | Document (202 KB) | BibTeX

    Recompression: New Approach to Word Equations and Context Unification (Invited Talk)
    Authors: Jez, Artur

    Abstract | Document (273 KB) | BibTeX

    Discrete Logarithms in Small Characteristic Finite Fields: a Survey of Recent Advances (Invited Talk)
    Authors: Joux, Antoine

    Abstract | Document (233 KB) | BibTeX

    Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk)
    Authors: Tantau, Till

    Abstract | Document (333 KB) | BibTeX

    Split Contraction: The Untold Story
    Authors: Agrawal, Akanksha ; Lokshtanov, Daniel ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (653 KB) | BibTeX

    The Operator Approach to Entropy Games
    Authors: Akian, Marianne ; Gaubert, Stéphane ; Grand-Clément, Julien ; Guillaud, Jérémie

    Abstract | Document (619 KB) | BibTeX

    Parameterized Complexity of Small Weight Automorphisms
    Authors: Arvind, Vikraman ; Köbler, Johannes ; Kuhnert, Sebastian ; Torán, Jacobo

    Abstract | Document (561 KB) | BibTeX

    What Can Be Verified Locally?
    Authors: Balliu, Alkida ; D'Angelo, Gianlorenzo ; Fraigniaud, Pierre ; Olivetti, Dennis

    Abstract | Document (559 KB) | BibTeX

    Improved Time-Space Trade-Offs for Computing Voronoi Diagrams
    Authors: Banyassady, Bahareh ; Korman, Matias ; Mulzer, Wolfgang ; van Renssen, André ; Roeloffzen, Marcel ; Seiferth, Paul ; Stein, Yannik

    Abstract | Document (591 KB) | BibTeX

    Energy-Efficient Delivery by Heterogeneous Mobile Agents
    Authors: Bärtschi, Andreas ; Chalopin, Jérémie ; Das, Shantanu ; Disser, Yann ; Graf, Daniel ; Hackfeld, Jan ; Penna, Paolo

    Abstract | Document (735 KB) | BibTeX

    Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams
    Authors: Bera, Suman K. ; Chakrabarti, Amit

    Abstract | Document (574 KB) | BibTeX

    On Polynomial Approximations Over Z/2^kZ*
    Authors: Bhrushundi, Abhishek ; Harsha, Prahladh ; Srinivasan, Srikanth

    Abstract | Document (584 KB) | BibTeX

    Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games
    Authors: Bilò, Vittorio ; Mavronicolas, Marios

    Abstract | Document (575 KB) | BibTeX

    On Büchi One-Counter Automata
    Authors: Böhm, Stanislav ; Göller, Stefan ; Halfon, Simon ; Hofman, Piotr

    Abstract | Document (565 KB) | BibTeX

    Optimizing Tree Decompositions in MSO
    Authors: Bojanczyk, Mikolaj ; Pilipczuk, Michal

    Abstract | Document (949 KB) | BibTeX

    Complexity of Token Swapping and its Variants
    Authors: Bonnet, Édouard ; Miltzow, Tillmann ; Rzazewski, Pawel

    Abstract | Document (700 KB) | BibTeX

    Monte Carlo Computability
    Authors: Brattka, Vasco ; Hölzl, Rupert ; Kuyper, Rutger

    Abstract | Document (556 KB) | BibTeX

    The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex
    Authors: Burton, Benjamin ; Cabello, Sergio ; Kratsch, Stefan ; Pettersson, William

    Abstract | Document (627 KB) | BibTeX

    On Long Words Avoiding Zimin Patterns
    Authors: Carayol, Arnaud ; Göller, Stefan

    Abstract | Document (529 KB) | BibTeX

    Extended Learning Graphs for Triangle Finding
    Authors: Carette, Titouan ; Laurière, Mathieu ; Magniez, Frédéric

    Abstract | Document (556 KB) | BibTeX

    Lower Bounds for Elimination via Weak Regularity
    Authors: Chattopadhyay, Arkadev ; Dvorák, Pavel ; Koucký, Michal ; Loff, Bruno ; Mukhopadhyay, Sagnik

    Abstract | Document (553 KB) | BibTeX

    Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix
    Authors: Chen, Lin ; Marx, Dániel ; Ye, Deshi ; Zhang, Guochuan

    Abstract | Document (562 KB) | BibTeX

    Fractional Coverings, Greedy Coverings, and Rectifier Networks
    Authors: Chistikov, Dmitry ; Iván, Szabolcs ; Lubiw, Anna ; Shallit, Jeffrey

    Abstract | Document (626 KB) | BibTeX

    Separability of Reachability Sets of Vector Addition Systems
    Authors: Clemente, Lorenzo ; Czerwinski, Wojciech ; Lasota, Slawomir ; Paperman, Charles

    Abstract | Document (512 KB) | BibTeX

    Counting Edge-Injective Homomorphisms and Matchings on Restricted Graph Classes
    Authors: Curticapean, Radu ; Dell, Holger ; Roth, Marc

    Abstract | Document (627 KB) | BibTeX

    Robust and Adaptive Search
    Authors: Disser, Yann ; Kratsch, Stefan

    Abstract | Document (554 KB) | BibTeX

    Graphic TSP in Cubic Graphs
    Authors: Dvorák, Zdenek ; Král, Daniel ; Mohar, Bojan

    Abstract | Document (507 KB) | BibTeX

    Independent Sets near the Lower Bound in Bounded Degree Graphs
    Authors: Dvorák, Zdenek ; Lidický, Bernard

    Abstract | Document (476 KB) | BibTeX

    Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem
    Authors: Fijalkow, Nathanaël ; Ohlmann, Pierre ; Ouaknine, Joël ; Pouly, Amaury ; Worrell, James

    Abstract | Document (463 KB) | BibTeX

    The First-Order Logic of Hyperproperties
    Authors: Finkbeiner, Bernd ; Zimmermann, Martin

    Abstract | Document (468 KB) | BibTeX

    Improving and Extending the Testing of Distributions for Shape-Restricted Properties
    Authors: Fischer, Eldar ; Lachish, Oded ; Vasudev, Yadu

    Abstract | Document (555 KB) | BibTeX

    Matrix Rigidity from the Viewpoint of Parameterized Complexity
    Authors: Fomin, Fedor V. ; Lokshtanov, Daniel ; Meesum, S. M. ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (506 KB) | BibTeX

    Deterministic Regular Expressions with Back-References
    Authors: Freydenberger, Dominik D. ; Schmid, Markus L.

    Abstract | Document (566 KB) | BibTeX

    On the Decomposition of Finite-Valued Streaming String Transducers
    Authors: Gallot, Paul ; Muscholl, Anca ; Puppis, Gabriele ; Salvati, Sylvain

    Abstract | Document (578 KB) | BibTeX

    Circuit Evaluation for Finite Semirings
    Authors: Ganardi, Moses ; Hucke, Danny ; König, Daniel ; Lohrey, Markus

    Abstract | Document (527 KB) | BibTeX

    Combining Treewidth and Backdoors for CSP
    Authors: Ganian, Robert ; Ramanujan, M. S. ; Szeider, Stefan

    Abstract | Document (706 KB) | BibTeX

    On the Complexity of Partial Derivatives
    Authors: Garcia-Marco, Ignacio ; Koiran, Pascal ; Pecatte, Timothée ; Thomassé, Stéphan

    Abstract | Document (517 KB) | BibTeX

    Set Membership with Non-Adaptive Bit Probes
    Authors: Garg, Mohit ; Radhakrishnan, Jaikumar

    Abstract | Document (509 KB) | BibTeX

    Pro-Aperiodic Monoids via Saturated Models
    Authors: van Gool, Samuel J. ; Steinberg, Benjamin

    Abstract | Document (526 KB) | BibTeX

    Trimming and Gluing Gray Codes
    Authors: Gregor, Petr ; Mütze, Torsten

    Abstract | Document (814 KB) | BibTeX

    Mixing of Permutations by Biased Transposition
    Authors: Haddadan, Shahrzad ; Winkler, Peter

    Abstract | Document (698 KB) | BibTeX

    Efficient Quantum Walk on the Grid with Multiple Marked Elements
    Authors: Hoyer, Peter ; Komeili, Mojtaba

    Abstract | Document (484 KB) | BibTeX

    On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables
    Authors: Itsykson, Dmitry ; Knop, Alexander ; Romashchenko, Andrey ; Sokolov, Dmitry

    Abstract | Document (509 KB) | BibTeX

    Multiple Random Walks on Paths and Grids
    Authors: Ivaskovic, Andrej ; Kosowski, Adrian ; Pajak, Dominik ; Sauerwald, Thomas

    Abstract | Document (511 KB) | BibTeX

    On the Size of Lempel-Ziv and Lyndon Factorizations
    Authors: Kärkkäinen, Juha ; Kempa, Dominik ; Nakashima, Yuto ; Puglisi, Simon J. ; Shur, Arseny M.

    Abstract | Document (514 KB) | BibTeX

    Voting and Bribing in Single-Exponential Time
    Authors: Knop, Dusan ; Koutecký, Martin ; Mnich, Matthias

    Abstract | Document (633 KB) | BibTeX

    A Complexity Dichotomy for Poset Constraint Satisfaction
    Authors: Kompatscher, Michael ; Pham, Trung Van

    Abstract | Document (480 KB) | BibTeX

    Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs
    Authors: Kreutzer, Stephan ; Rabinovich, Roman ; Siebertz, Sebastian ; Weberstädt, Grischa

    Abstract | Document (509 KB) | BibTeX

    Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
    Authors: Kulikov, Alexander S. ; Podolskii, Vladimir V.

    Abstract | Document (545 KB) | BibTeX

    Minkowski Games
    Authors: Le Roux, Stéphane ; Pauly, Arno ; Raskin, Jean-François

    Abstract | Document (581 KB) | BibTeX

    On the Sensitivity Complexity of k-Uniform Hypergraph Properties
    Authors: Li, Qian ; Sun, Xiaoming

    Abstract | Document (501 KB) | BibTeX

    The Complexity of Knapsack in Graph Groups
    Authors: Lohrey, Markus ; Zetzsche, Georg

    Abstract | Document (574 KB) | BibTeX

    Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension
    Authors: Lutz, Jack H. ; Lutz, Neil

    Abstract | Document (495 KB) | BibTeX

    On the Synchronisation Problem over Cellular Automata
    Authors: Richard, Gaétan

    Abstract | Document (528 KB) | BibTeX

    Word Equations Where a Power Equals a Product of Powers
    Authors: Saarela, Aleksi

    Abstract | Document (438 KB) | BibTeX

    Improved Distance Queries and Cycle Counting by Frobenius Normal Form
    Authors: Sankowski, Piotr ; Wegrzycki, Karol

    Abstract | Document (515 KB) | BibTeX

    Lower Bounds on Key Derivation for Square-Friendly Applications
    Authors: Skorski, Maciej

    Abstract | Document (521 KB) | BibTeX

    List Approximation for Increasing Kolmogorov Complexity
    Authors: Zimand, Marius

    Abstract | Document (465 KB) | BibTeX

    		  



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