STACS 2014 March 5-8, 2014, Lyon, France

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)



Ernst W. Mayr and Natacha Portier (Eds.)
ISBN 978-3-939897-65-1, LIPICS Vol. 25 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 25 MB)
Search Publication Server


Authors
  • Adamczyk, Marek
  • Anderson, Matthew
  • Angel, Eric
  • Antoniadis, Antonios
  • Araujo, Julio
  • Azar, Yossi
  • Aziz, Haris
  • Bacquey, Nicolas
  • Bampis, Evripidis
  • Bannai, Hideo
  • Barcelo, Neal
  • Bauwens, Bruno
  • Bekos, Michael A.
  • Berenbrink, Petra
  • Blanchet-Sadri, Francine
  • Bodnar, Michelle
  • Boyar, Joan
  • Bringmann, Karl
  • Bruyčre, Véronique
  • Cao, Yixin
  • Chau, Vincent
  • Chen, Jian-Jia
  • Chillara, Suryajith
  • Consuegra, Mario
  • Cygan, Marek
  • Dawar, Anuj
  • de Keijzer, Bart
  • Dereniowski, Dariusz
  • De Winkle, Benjamin
  • Disser, Yann
  • Drange, Pal Gronas
  • Englert, Matthias
  • Ergün, Funda
  • Esparza, Javier
  • Figueira, Diego
  • Filiot, Emmanuel
  • Filmus, Yuval
  • Fomin, Fedor V.
  • Göbel, Andreas
  • Gamzu, Iftah
  • Garnero, Valentin
  • Gavinsky, Dmitry
  • Gawrychowski, Pawel
  • Goldberg, Leslie Ann
  • Gronemann, Martin
  • Hoyrup, Mathieu
  • Huschenbett, Martin
  • I, Tomohiro
  • Inenaga, Shunsuke
  • Ivanyos, Gábor
  • Iwama, Kazuo
  • Jeandel, Emmanuel
  • Jelinek, Tomas
  • Jez, Artur
  • Kärkkäinen, Juha
  • Kötzing, Timo
  • Kamali, Shahin
  • Kao, Mong-Jen
  • Karpinski, Marek
  • Kawarabayashi, Ken-ichi
  • Kayal, Neeraj
  • Kempa, Dominik
  • Kidron, Eytan
  • Klaas, Marcus
  • Klimm, Max
  • Kling, Peter
  • Kociumaka, Tomasz
  • Komm, Dennis
  • Kosowski, Adrian
  • Kothari, Robin
  • Královic, Rastislav
  • Královic, Richard
  • Kufleitner, Manfred
  • López-Ortiz, Alejandro
  • Larsen, Kim S.
  • Lauria, Massimo
  • Lee, D.T.
  • Lewenstein, Moshe
  • Libkin, Leonid
  • Lohrey, Markus
  • Mömke, Tobias
  • Mallmann-Trenn, Frederik
  • Manea, Florin
  • Marx, Dániel
  • Mayr, Ernst W.
  • Megow, Nicole
  • Miksa, Mladen
  • Miltersen, Peter Bro
  • Mitchell, John C.
  • Monin, Benoit
  • Mukhopadhyay, Partha
  • Mustafa, Nabil H.
  • Nagao, Atsuki
  • Nekrich, Yakov
  • Nguyen, Dung T.
  • Nies, André
  • Nisse, Nicolas
  • Nordström, Jakob
  • Nowotka, Dirk
  • Nugent, Michael
  • Pérennes, Stéphane
  • Pajak, Dominik
  • Paul, Christophe
  • Pierrot, Adeline
  • Pilipczuk, Michal
  • Portier, Natacha
  • Pruhs, Kirk
  • Pudlák, Pavel
  • Qiao, Youming
  • Raftopoulou, Chrysanthi N.
  • Randour, Mickael
  • Raskin, Jean-François
  • Ray, Saurabh
  • Richerby, David
  • Rossin, Dominique
  • Rutter, Ignaz
  • Sadeqi Azer, Erfan
  • Santha, Miklos
  • Sau, Ignasi
  • Sauerwald, Thomas
  • Schäfer, Guido
  • Scquizzato, Michele
  • Segoufin, Luc
  • Selman, Alan L.
  • Silvestri, Francesco
  • Skutella, Martin
  • Stauffer, Alexandre
  • Stiller, Sebastian
  • Sun, He
  • Sviridenko, Maxim
  • Takeda, Masayuki
  • Thilikos, Dimitrios M.
  • Thorup, Mikkel
  • Uetz, Marc
  • Uppman, Hannes
  • Uznanski, Przemyslaw
  • Villanger, Yngve
  • Vinyals, Marc
  • Vitter, Jeffrey Scott
  • Wagner, Dorothea
  • Ward, Justin
  • Watson, Thomas
  • Yamamoto, Jun'ichi
  • Zetzsche, Georg
  • Zimmerman, Joe

  •   
    Frontmatter, Table of Contents, Preface, Conference Organization
    Authors: Mayr, Ernst W. ; Portier, Natacha

    Abstract | Document (517 KB) | BibTeX

    Keeping a Crowd Safe: On the Complexity of Parameterized Verification (Invited Talk)
    Authors: Esparza, Javier

    Abstract | Document (532 KB) | BibTeX

    Semi-algebraic geometry in computational game theory - a consumer's perspective (Invited Talk)
    Authors: Miltersen, Peter Bro

    Abstract | Document (445 KB) | BibTeX

    A glimpse on constant delay enumeration (Invited Talk)
    Authors: Segoufin, Luc

    Abstract | Document (569 KB) | BibTeX

    Arithmetic Circuit Complexity (Tutorial)
    Authors: Kayal, Neeraj

    Abstract | Document (354 KB) | BibTeX

    Submodular Stochastic Probing on Matroids
    Authors: Adamczyk, Marek ; Sviridenko, Maxim ; Ward, Justin

    Abstract | Document (627 KB) | BibTeX

    On Symmetric Circuits and Fixed-Point Logics
    Authors: Anderson, Matthew ; Dawar, Anuj

    Abstract | Document (613 KB) | BibTeX

    Throughput Maximization in the Speed-Scaling Setting
    Authors: Angel, Eric ; Bampis, Evripidis ; Chau, Vincent

    Abstract | Document (670 KB) | BibTeX

    Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules
    Authors: Antoniadis, Antonios ; Barcelo, Neal ; Consuegra, Mario ; Kling, Peter ; Nugent, Michael ; Pruhs, Kirk ; Scquizzato, Michele

    Abstract | Document (668 KB) | BibTeX

    Weighted Coloring in Trees
    Authors: Araujo, Julio ; Nisse, Nicolas ; Pérennes, Stéphane

    Abstract | Document (742 KB) | BibTeX

    Generalized Reordering Buffer Management
    Authors: Azar, Yossi ; Englert, Matthias ; Gamzu, Iftah ; Kidron, Eytan

    Abstract | Document (550 KB) | BibTeX

    Shapley meets Shapley
    Authors: Aziz, Haris ; de Keijzer, Bart

    Abstract | Document (713 KB) | BibTeX

    Complexity classes on spatially periodic Cellular Automata
    Authors: Bacquey, Nicolas

    Abstract | Document (590 KB) | BibTeX

    Asymmetry of the Kolmogorov complexity of online predicting odd and even bits
    Authors: Bauwens, Bruno

    Abstract | Document (655 KB) | BibTeX

    Two-Page Book Embeddings of 4-Planar Graphs
    Authors: Bekos, Michael A. ; Gronemann, Martin ; Raftopoulou, Chrysanthi N.

    Abstract | Document (768 KB) | BibTeX

    Palindrome Recognition In The Streaming Model
    Authors: Berenbrink, Petra ; Ergün, Funda ; Mallmann-Trenn, Frederik ; Sadeqi Azer, Erfan

    Abstract | Document (807 KB) | BibTeX

    New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings
    Authors: Blanchet-Sadri, Francine ; Bodnar, Michelle ; De Winkle, Benjamin

    Abstract | Document (656 KB) | BibTeX

    Online Bin Packing with Advice
    Authors: Boyar, Joan ; Kamali, Shahin ; Larsen, Kim S. ; López-Ortiz, Alejandro

    Abstract | Document (608 KB) | BibTeX

    Balls into bins via local search: cover time and maximum load
    Authors: Bringmann, Karl ; Sauerwald, Thomas ; Stauffer, Alexandre ; Sun, He

    Abstract | Document (618 KB) | BibTeX

    Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games
    Authors: Bruyčre, Véronique ; Filiot, Emmanuel ; Randour, Mickael ; Raskin, Jean-François

    Abstract | Document (842 KB) | BibTeX

    Chordal Editing is Fixed-Parameter Tractable
    Authors: Cao, Yixin ; Marx, Dániel

    Abstract | Document (704 KB) | BibTeX

    Online Dynamic Power Management with Hard Real-Time Guarantees
    Authors: Chen, Jian-Jia ; Kao, Mong-Jen ; Lee, D.T. ; Rutter, Ignaz ; Wagner, Dorothea

    Abstract | Document (720 KB) | BibTeX

    Depth-4 Lower Bounds, Determinantal Complexity: A Unified Approach
    Authors: Chillara, Suryajith ; Mukhopadhyay, Partha

    Abstract | Document (655 KB) | BibTeX

    Constant Factor Approximation for Capacitated k-Center with Outliers
    Authors: Cygan, Marek ; Kociumaka, Tomasz

    Abstract | Document (635 KB) | BibTeX

    Bounds on the Cover Time of Parallel Rotor Walks
    Authors: Dereniowski, Dariusz ; Kosowski, Adrian ; Pajak, Dominik ; Uznanski, Przemyslaw

    Abstract | Document (708 KB) | BibTeX

    Packing a Knapsack of Unknown Capacity
    Authors: Disser, Yann ; Klimm, Max ; Megow, Nicole ; Stiller, Sebastian

    Abstract | Document (572 KB) | BibTeX

    Exploring Subexponential Parameterized Complexity of Completion Problems
    Authors: Drange, Pal Gronas ; Fomin, Fedor V. ; Pilipczuk, Michal ; Villanger, Yngve

    Abstract | Document (703 KB) | BibTeX

    From Small Space to Small Width in Resolution
    Authors: Filmus, Yuval ; Lauria, Massimo ; Miksa, Mladen ; Nordström, Jakob ; Vinyals, Marc

    Abstract | Document (569 KB) | BibTeX

    Explicit Linear Kernels via Dynamic Programming
    Authors: Garnero, Valentin ; Paul, Christophe ; Sau, Ignasi ; Thilikos, Dimitrios M.

    Abstract | Document (744 KB) | BibTeX

    Partition Expanders
    Authors: Gavinsky, Dmitry ; Pudlák, Pavel

    Abstract | Document (659 KB) | BibTeX

    Testing Generalised Freeness of Words
    Authors: Gawrychowski, Pawel ; Manea, Florin ; Nowotka, Dirk

    Abstract | Document (694 KB) | BibTeX

    Counting Homomorphisms to Cactus Graphs Modulo 2
    Authors: Göbel, Andreas ; Goldberg, Leslie Ann ; Richerby, David

    Abstract | Document (607 KB) | BibTeX

    Irreversible computable functions
    Authors: Hoyrup, Mathieu

    Abstract | Document (593 KB) | BibTeX

    Ehrenfeucht-Fraďssé Games on Omega-Terms
    Authors: Huschenbett, Martin ; Kufleitner, Manfred

    Abstract | Document (693 KB) | BibTeX

    Faster Sparse Suffix Sorting
    Authors: I, Tomohiro ; Kärkkäinen, Juha ; Kempa, Dominik

    Abstract | Document (620 KB) | BibTeX

    Generalized Wong sequences and their applications to Edmonds' problems
    Authors: Ivanyos, Gábor ; Karpinski, Marek ; Qiao, Youming ; Santha, Miklos

    Abstract | Document (684 KB) | BibTeX

    Read-Once Branching Programs for Tree Evaluation Problems
    Authors: Iwama, Kazuo ; Nagao, Atsuki

    Abstract | Document (754 KB) | BibTeX

    Computability of the entropy of one-tape Turing machines
    Authors: Jeandel, Emmanuel

    Abstract | Document (540 KB) | BibTeX

    Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players
    Authors: Jelinek, Tomas ; Klaas, Marcus ; Schäfer, Guido

    Abstract | Document (683 KB) | BibTeX

    Approximation of smallest linear tree grammar
    Authors: Jez, Artur ; Lohrey, Markus

    Abstract | Document (647 KB) | BibTeX

    Coloring 3-colorable graphs with o(n^{1/5}) colors
    Authors: Kawarabayashi, Ken-ichi ; Thorup, Mikkel

    Abstract | Document (708 KB) | BibTeX

    Randomized Online Algorithms with High Probability Guarantees
    Authors: Komm, Dennis ; Královic, Rastislav ; Královic, Richard ; Mömke, Tobias

    Abstract | Document (647 KB) | BibTeX

    An optimal quantum algorithm for the oracle identification problem
    Authors: Kothari, Robin

    Abstract | Document (606 KB) | BibTeX

    A Solution to Wiehagen's Thesis
    Authors: Kötzing, Timo

    Abstract | Document (591 KB) | BibTeX

    Space-Efficient String Indexing for Wildcard Pattern Matching
    Authors: Lewenstein, Moshe ; Nekrich, Yakov ; Vitter, Jeffrey Scott

    Abstract | Document (629 KB) | BibTeX

    Synchronizing Relations on Words
    Authors: Figueira, Diego ; Libkin, Leonid

    Abstract | Document (909 KB) | BibTeX

    On Boolean closed full trios and rational Kripke frames
    Authors: Lohrey, Markus ; Zetzsche, Georg

    Abstract | Document (559 KB) | BibTeX

    Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)
    Authors: Marx, Dániel ; Pilipczuk, Michal

    Abstract | Document (680 KB) | BibTeX

    Data-Oblivious Data Structures
    Authors: Mitchell, John C. ; Zimmerman, Joe

    Abstract | Document (596 KB) | BibTeX

    Higher randomness and forcing with closed sets
    Authors: Monin, Benoit

    Abstract | Document (658 KB) | BibTeX

    Near-Optimal Generalisations of a Theorem of Macbeath
    Authors: Mustafa, Nabil H. ; Ray, Saurabh

    Abstract | Document (632 KB) | BibTeX

    Non-autoreducible Sets for NEXP
    Authors: Nguyen, Dung T. ; Selman, Alan L.

    Abstract | Document (627 KB) | BibTeX

    Differentiability of polynomial time computable functions
    Authors: Nies, André

    Abstract | Document (580 KB) | BibTeX

    2-Stack Sorting is polynomial
    Authors: Pierrot, Adeline ; Rossin, Dominique

    Abstract | Document (707 KB) | BibTeX

    Communication Lower Bounds for Distributed-Memory Computations
    Authors: Scquizzato, Michele ; Silvestri, Francesco

    Abstract | Document (579 KB) | BibTeX

    Stochastic Scheduling on Unrelated Machines
    Authors: Skutella, Martin ; Sviridenko, Maxim ; Uetz, Marc

    Abstract | Document (629 KB) | BibTeX

    Computational Complexity of the Extended Minimum Cost Homomorphism Problem on Three-Element Domains
    Authors: Uppman, Hannes

    Abstract | Document (607 KB) | BibTeX

    The Complexity of Deciding Statistical Properties of Samplable Distributions
    Authors: Watson, Thomas

    Abstract | Document (637 KB) | BibTeX

    Faster Compact On-Line Lempel-Ziv Factorization
    Authors: Yamamoto, Jun'ichi ; I, Tomohiro ; Bannai, Hideo ; Inenaga, Shunsuke ; Takeda, Masayuki

    Abstract | Document (628 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint Published by LZI