STACS 2018 February 28 to March 3, 2018 - Caen, France

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)



Rolf Niedermeier and Brigitte Vallée (Eds.)
ISBN 978-3-95977-062-0, LIPICS Vol. 96 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 24 MB)
Search Publication Server

Authors
  • Adamaszek, Anna
  • Adler, Isolde
  • Agrawal, Akanksha
  • Ambainis, Andris
  • Antoniadis, Antonios
  • Bannach, Max
  • Belmonte, Rémy
  • Berkholz, Christoph
  • Beyersdorff, Olaf
  • Bienvenu, Laurent
  • Bilò, Davide
  • Blinkhorn, Joshua
  • Blondin, Michael
  • Bollig, Benedikt
  • Bouyer, Patricia
  • Bressan, Marco
  • Carbonnel, Clément
  • Charron-Bost, Bernadette
  • Chillara, Suryajith
  • Choudhary, Keerti
  • Clifford, Raphaël
  • Cohen, David A.
  • Cooper, Martin C.
  • Das, Debarati
  • Demaine, Erik D.
  • Demirci, Gökalp
  • Downey, Rodney
  • Dvorák, Pavel
  • Egri, László
  • Eiben, Eduard
  • Eisenstat, Sarah
  • Esparza, Javier
  • Feldmann, Andreas Emil
  • Fleischer, Lukas
  • Fortin, Marie
  • Ganardi, Moses
  • Ganian, Robert
  • Gardy, Patrick
  • Gaspers, Serge
  • Gastin, Paul
  • Geissmann, Barbara
  • Giakkoupis, George
  • Gourdel, Garance
  • Grønlund, Allan
  • Gualà, Luciano
  • Harwath, Frederik
  • Hirai, Hiroshi
  • Hitchcock, John M.
  • Hoffmann, Henry
  • Huang, Shenwei
  • Hucke, Danny
  • Iwamasa, Yuni
  • Iwata, Yoichi
  • Jaax, Stefan
  • Jaffke, Lars
  • Jäger, Sven
  • Kim, David H. K.
  • Kiyomi, Masashi
  • Klute, Fabian
  • Knop, Dušan
  • Köcher, Chris
  • Kociumaka, Tomasz
  • Kokainis, Martins
  • König, Daniel
  • Kosolobov, Dmitry
  • Koucký, Michal
  • Kufleitner, Manfred
  • Kumar, Amit
  • Kumar, Mithilesh
  • Kuperberg, Denis
  • Kwon, O-joung
  • Lampis, Michael
  • Larose, Benoit
  • Larsen, Kasper Green
  • Lenzner, Pascal
  • Leucci, Stefano
  • Limaye, Nutan
  • Liu, Chih-Hung
  • Lohrey, Markus
  • Lokshtanov, Daniel
  • Luttenberger, Michael
  • Mahajan, Meena
  • Majumdar, Anirban
  • Mamouras, Konstantinos
  • Markey, Nicolas
  • Martin, Barnaby
  • Marx, Dániel
  • Masarík, Tomáš
  • Mazowiecki, Filip
  • Misra, Pranabendu
  • Mitsou, Valia
  • Mömke, Tobias
  • Moran, Shlomo
  • Mouawad, Amer E.
  • Murota, Kazuo
  • Niedermeier, Rolf
  • Nies, André
  • Ogasawara, Tomoaki
  • Ohsaka, Naoto
  • Onodera, Taku
  • Ono, Hirotaka
  • Ordyniak, Sebastian
  • Otachi, Yota
  • Palenta, Raphaela
  • Panolan, Fahad
  • Parter, Merav
  • Parys, Pawel
  • Paulusma, Daniel
  • Penna, Paolo
  • Peserico, Enoch
  • Pous, Damien
  • Pretto, Luca
  • Proietti, Guido
  • Prusis, Krisjanis
  • Radoszewski, Jakub
  • Rajasekaran, Aayush
  • Riveros, Cristian
  • Rudoy, Mikhail
  • Rytter, Wojciech
  • Rzazewski, Pawel
  • Saks, Michael
  • Salvy, Bruno
  • Saurabh, Saket
  • Schweitzer, Pascal
  • Seidl, Helmut
  • Shafei, Hadi
  • Shallit, Jeffrey
  • Shibuya, Tetsuo
  • Shur, Arseny
  • Siebertz, Sebastian
  • Simon, Hans U.
  • Skutella, Martin
  • Smith, Tim
  • Srinivasan, Srikanth
  • Starikovskaya, Tatiana
  • Stephan, Frank
  • Szykula, Marek
  • Takahashi, Yasuhiro
  • Tani, Seiichiro
  • Tantau, Till
  • Tarui, Jun
  • Telle, Jan Arne
  • Tell, Roei
  • Toufar, Tomáš
  • Vallée, Brigitte
  • Veselý, Pavel
  • Vihrovs, Jevgenijs
  • Walen, Tomasz
  • Woeginger, Gerhard J.
  • Woelfel, Philipp
  • Zehavi, Meirav
  • Zetzsche, Georg
  • Zivny, Stanislav
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Niedermeier, Rolf ; Vallée, Brigitte

    Abstract | Document (428 KB) | BibTeX

    Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation
    Authors: Salvy, Bruno

    Abstract | Document (402 KB) | BibTeX

    Lower Bound Techniques for QBF Proof Systems
    Authors: Mahajan, Meena

    Abstract | Document (436 KB) | BibTeX

    On the Positive Calculus of Relations with Transitive Closure
    Authors: Pous, Damien

    Abstract | Document (508 KB) | BibTeX

    The Open Shop Scheduling Problem
    Authors: Woeginger, Gerhard J.

    Abstract | Document (468 KB) | BibTeX

    Approximating Airports and Railways
    Authors: Adamaszek, Anna ; Antoniadis, Antonios ; Kumar, Amit ; Mömke, Tobias

    Abstract | Document (806 KB) | BibTeX

    Property Testing for Bounded Degree Databases
    Authors: Adler, Isolde ; Harwath, Frederik

    Abstract | Document (479 KB) | BibTeX

    Erdös-Pósa Property of Obstructions to Interval Graphs
    Authors: Agrawal, Akanksha ; Lokshtanov, Daniel ; Misra, Pranabendu ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (622 KB) | BibTeX

    All Classical Adversary Methods are Equivalent for Total Functions
    Authors: Ambainis, Andris ; Kokainis, Martins ; Prusis, Krisjanis ; Vihrovs, Jevgenijs

    Abstract | Document (523 KB) | BibTeX

    Computing Hitting Set Kernels By AC^0-Circuits
    Authors: Bannach, Max ; Tantau, Till

    Abstract | Document (601 KB) | BibTeX

    Parameterized (Approximate) Defective Coloring
    Authors: Belmonte, Rémy ; Lampis, Michael ; Mitsou, Valia

    Abstract | Document (545 KB) | BibTeX

    The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs
    Authors: Berkholz, Christoph

    Abstract | Document (522 KB) | BibTeX

    Genuine Lower Bounds for QBF Expansion
    Authors: Beyersdorff, Olaf ; Blinkhorn, Joshua

    Abstract | Document (488 KB) | BibTeX

    Efficient Oracles and Routing Schemes for Replacement Paths
    Authors: Bilò, Davide ; Choudhary, Keerti ; Gualà, Luciano ; Leucci, Stefano ; Parter, Merav ; Proietti, Guido

    Abstract | Document (783 KB) | BibTeX

    On the Tree Conjecture for the Network Creation Game
    Authors: Bilò, Davide ; Lenzner, Pascal

    Abstract | Document (698 KB) | BibTeX

    On Low for Speed Oracles
    Authors: Bienvenu, Laurent ; Downey, Rodney

    Abstract | Document (528 KB) | BibTeX

    Large Flocks of Small Birds: on the Minimal Size of Population Protocols
    Authors: Blondin, Michael ; Esparza, Javier ; Jaax, Stefan

    Abstract | Document (591 KB) | BibTeX

    Communicating Finite-State Machines and Two-Variable Logic
    Authors: Bollig, Benedikt ; Fortin, Marie ; Gastin, Paul

    Abstract | Document (635 KB) | BibTeX

    On Approximating the Stationary Distribution of Time-reversible Markov Chains
    Authors: Bressan, Marco ; Peserico, Enoch ; Pretto, Luca

    Abstract | Document (606 KB) | BibTeX

    On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
    Authors: Carbonnel, Clément ; Cohen, David A. ; Cooper, Martin C. ; Zivny, Stanislav

    Abstract | Document (518 KB) | BibTeX

    The Firing Squad Problem Revisited
    Authors: Charron-Bost, Bernadette ; Moran, Shlomo

    Abstract | Document (551 KB) | BibTeX

    Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
    Authors: Chillara, Suryajith ; Limaye, Nutan ; Srinivasan, Srikanth

    Abstract | Document (610 KB) | BibTeX

    Upper and Lower Bounds for Dynamic Data Structures on Strings
    Authors: Clifford, Raphaël ; Grønlund, Allan ; Larsen, Kasper Green ; Starikovskaya, Tatiana

    Abstract | Document (538 KB) | BibTeX

    Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
    Authors: Das, Debarati ; Koucký, Michal ; Saks, Michael

    Abstract | Document (507 KB) | BibTeX

    Solving the Rubik's Cube Optimally is NP-complete
    Authors: Demaine, Erik D. ; Eisenstat, Sarah ; Rudoy, Mikhail

    Abstract | Document (662 KB) | BibTeX

    Approximation Algorithms for Scheduling with Resource and Precedence Constraints
    Authors: Demirci, Gökalp ; Hoffmann, Henry ; Kim, David H. K.

    Abstract | Document (552 KB) | BibTeX

    Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
    Authors: Dvorák, Pavel ; Feldmann, Andreas Emil ; Knop, Dušan ; Masarík, Tomáš ; Toufar, Tomáš ; Veselý, Pavel

    Abstract | Document (563 KB) | BibTeX

    Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization
    Authors: Egri, László ; Marx, Dániel ; Rzazewski, Pawel

    Abstract | Document (564 KB) | BibTeX

    Small Resolution Proofs for QBF using Dependency Treewidth
    Authors: Eiben, Eduard ; Ganian, Robert ; Ordyniak, Sebastian

    Abstract | Document (517 KB) | BibTeX

    Lossy Kernels for Connected Dominating Set on Sparse Graphs
    Authors: Eiben, Eduard ; Kumar, Mithilesh ; Mouawad, Amer E. ; Panolan, Fahad ; Siebertz, Sebastian

    Abstract | Document (557 KB) | BibTeX

    The Intersection Problem for Finite Monoids
    Authors: Fleischer, Lukas ; Kufleitner, Manfred

    Abstract | Document (577 KB) | BibTeX

    Automata Theory on Sliding Windows
    Authors: Ganardi, Moses ; Hucke, Danny ; König, Daniel ; Lohrey, Markus ; Mamouras, Konstantinos

    Abstract | Document (569 KB) | BibTeX

    Knapsack Problems for Wreath Products
    Authors: Ganardi, Moses ; König, Daniel ; Lohrey, Markus ; Zetzsche, Georg

    Abstract | Document (551 KB) | BibTeX

    On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
    Authors: Ganian, Robert ; Klute, Fabian ; Ordyniak, Sebastian

    Abstract | Document (691 KB) | BibTeX

    Dependences in Strategy Logic
    Authors: Gardy, Patrick ; Bouyer, Patricia ; Markey, Nicolas

    Abstract | Document (615 KB) | BibTeX

    Colouring Square-Free Graphs without Long Induced Paths
    Authors: Gaspers, Serge ; Huang, Shenwei ; Paulusma, Daniel

    Abstract | Document (507 KB) | BibTeX

    Optimal Dislocation with Persistent Errors in Subquadratic Time
    Authors: Geissmann, Barbara ; Leucci, Stefano ; Liu, Chih-Hung ; Penna, Paolo

    Abstract | Document (676 KB) | BibTeX

    An Improved Bound for Random Binary Search Trees with Concurrent Insertions
    Authors: Giakkoupis, George ; Woelfel, Philipp

    Abstract | Document (502 KB) | BibTeX

    String Periods in the Order-Preserving Model
    Authors: Gourdel, Garance ; Kociumaka, Tomasz ; Radoszewski, Jakub ; Rytter, Wojciech ; Shur, Arseny ; Walen, Tomasz

    Abstract | Document (612 KB) | BibTeX

    Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection
    Authors: Hirai, Hiroshi ; Iwamasa, Yuni ; Murota, Kazuo ; Zivny, Stanislav

    Abstract | Document (606 KB) | BibTeX

    Nonuniform Reductions and NP-Completeness
    Authors: Hitchcock, John M. ; Shafei, Hadi

    Abstract | Document (463 KB) | BibTeX

    On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
    Authors: Iwata, Yoichi ; Ogasawara, Tomoaki ; Ohsaka, Naoto

    Abstract | Document (628 KB) | BibTeX

    A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width
    Authors: Jaffke, Lars ; Kwon, O-joung ; Telle, Jan Arne

    Abstract | Document (646 KB) | BibTeX

    Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling
    Authors: Jäger, Sven ; Skutella, Martin

    Abstract | Document (576 KB) | BibTeX

    Space-Efficient Algorithms for Longest Increasing Subsequence
    Authors: Kiyomi, Masashi ; Ono, Hirotaka ; Otachi, Yota ; Schweitzer, Pascal ; Tarui, Jun

    Abstract | Document (581 KB) | BibTeX

    Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid
    Authors: Köcher, Chris

    Abstract | Document (486 KB) | BibTeX

    Relations Between Greedy and Bit-Optimal LZ77 Encodings
    Authors: Kosolobov, Dmitry

    Abstract | Document (546 KB) | BibTeX

    Width of Non-deterministic Automata
    Authors: Kuperberg, Denis ; Majumdar, Anirban

    Abstract | Document (476 KB) | BibTeX

    Computing the Longest Common Prefix of a Context-free Language in Polynomial Time
    Authors: Luttenberger, Michael ; Palenta, Raphaela ; Seidl, Helmut

    Abstract | Document (560 KB) | BibTeX

    Surjective H-Colouring over Reflexive Digraphs
    Authors: Larose, Benoit ; Martin, Barnaby ; Paulusma, Daniel

    Abstract | Document (529 KB) | BibTeX

    Pumping Lemmas for Weighted Automata
    Authors: Mazowiecki, Filip ; Riveros, Cristian

    Abstract | Document (628 KB) | BibTeX

    Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations
    Authors: Nies, André ; Stephan, Frank

    Abstract | Document (454 KB) | BibTeX

    Succinct Oblivious RAM
    Authors: Onodera, Taku ; Shibuya, Tetsuo

    Abstract | Document (579 KB) | BibTeX

    Recursion Schemes and the WMSO+U Logic
    Authors: Parys, Pawel

    Abstract | Document (528 KB) | BibTeX

    Sums of Palindromes: an Approach via Automata
    Authors: Rajasekaran, Aayush ; Shallit, Jeffrey ; Smith, Tim

    Abstract | Document (482 KB) | BibTeX

    On the Containment Problem for Linear Sets
    Authors: Simon, Hans U.

    Abstract | Document (508 KB) | BibTeX

    Improving the Upper Bound on the Length of the Shortest Reset Word
    Authors: Szykula, Marek

    Abstract | Document (442 KB) | BibTeX

    Power of Uninitialized Qubits in Shallow Quantum Circuits
    Authors: Takahashi, Yasuhiro ; Tani, Seiichiro

    Abstract | Document (662 KB) | BibTeX

    Lower Bounds on Black-Box Reductions of Hitting to Density Estimation
    Authors: Tell, Roei

    Abstract | Document (546 KB) | BibTeX

    		  



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