Accepted Papers

STACS 2014 Accepted Papers

Mathieu HoyrupIrreversible computable functions
Francine Blanchet-Sadri, Michelle Bodnar and Benjamin De Winkle. New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings
Andre Nies. Differentiability of polynomial time computable functions
Junichi Yamamoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda. Faster Compact On-Line Lempel-Ziv Factorization
Timo KötzingA Solution to Wiehagen's Thesis
Ken-Ichi Kawarabayashi and Mikkel Thorup. Coloring 3-colorable graphs with o(n^{1/5}) colors
Thomas WatsonThe Complexity of Deciding Statistical Properties of Samplable Distributions
Nicolas Bacquey. Complexity classes on spatially periodic Cellular Automata
Emmanuel Jeandel. Computability of the entropy of one-tape Turing Machines
Dung Nguyen and Alan Selman. Non-autoreducible sets for NEXP
Martin SkutellaMaxim Sviridenko and Marc UetzStochastic Scheduling on Unrelated Machines
Yossi Azar, Matthias Englert, Iftah Gamzu and Eytan Kidron. Generalized Reordering Buffer Management
Dmitry Gavinsky and Pavel Pudlák. Partition Expanders
Suryajith Chillara and Partha Mukhopadhyay. Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach
Petra Berenbrink, Funda Ergün, Frederik Mallmann-Trenn and Erfan Sadeqi Azer. Palindrome Recognition In The Streaming Model
Andreas Goebel, Leslie Ann Goldberg and David Richerby. Counting Homomorphisms to Cactus Graphs Modulo 2
Tomohiro I, Juha Kärkkäinen and Dominik Kempa. Faster Sparse Suffix Sorting
Haris Aziz and Bart de KeijzerShapley Meets Shapley
Valentin GarneroChristophe PaulIgnasi Sau and Dimitrios M. ThilikosExplicit Linear Kernels via Dynamic Programming
Antonios Antoniadis, Neal Barcelo, Mario Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs and Michele ScquizzatoEfficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules
Michael Bekos, Martin Gronemann and Chrysanthi Raftopoulou. Two-Page Book Embeddings of 4-Planar Graphs
Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer and He Sun. Balls into bins via local search: cover time and maximum load
Marek Cygan and Tomasz KociumakaConstant Factor Approximation for Capacitated k-Center with Outliers
Pawel Gawrychowski, Florin Manea and Dirk NowotkaTesting Generalised Freeness of Words
Joan BoyarShahin KamaliKim S. Larsen and Alejandro Lopez-OrtizOnline Bin Packing with Advice
Artur Jeż and Markus LohreyApproximation of smallest linear tree grammar
Matthew Anderson and Anuj DawarOn Symmetric Circuits and Fixed-Point Logics
Kazuo Iwama and Atsuki Nagao. Read-Once Branching Programs for Tree Evaluation Problems
Gábor Ivanyos, Marek Karpinski, Youming Qiao and Miklos SanthaGeneralized Wong sequences and their applications to Edmonds' problems
Yann Disser, Max Klimm, Nicole Megow and Sebastian Stiller. Packing a Knapsack of Unknown Capacity
Julio Araujo, Nicolas Nisse and Stéphane Pérennes. Weighted Coloring in Trees
Diego Figueira and Leonid LibkinSynchronizing Relations on Words
Dániel Marx and Michał PilipczukEverything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)
Pål Grønås DrangeFedor V. FominMichał Pilipczuk and Yngve VillangerExploring Subexponential Parameterized Complexity of Completion Problems
Benoit MoninHigher randomness and forcing with closed sets
Michele Scquizzato and Francesco SilvestriCommunication Lower Bounds for Distributed-Memory Computations
Véronique BruyèreEmmanuel FiliotMickael Randour and Jean-François RaskinMeet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games
Yuval Filmus, Massimo LauriaMladen MiksaJakob Nordstrom and Marc VinyalsFrom Small Space to Small Width in Resolution
Eric Angel, Evripidis Bampis and Vincent Chau. Throughput Maximization in the Speed-Scaling Setting
Jian-Jia Chen, Mong-Jen KaoDer-Tsai LeeIgnaz Rutter and Dorothea WagnerOnline Dynamic Power Management with Hard Real-Time Guarantees
Robin KothariAn optimal quantum algorithm for the oracle identification problem
Dennis Komm, Tobias Moemke, Rastislav Kralovic and Richard Kralovic. Randomized Online Algorithms with High Probability Guarantees
Nabil Mustafa and Saurabh Ray. Near-Optimal Generalisations of a Theorem of Macbeath
Hannes Uppman. Computational Complexity of the Minimum Cost Homomorphism Problem on Three-Element Domains
Yixin Cao and Dániel MarxChordal Editing is Fixed-Parameter Tractable
Dariusz DereniowskiAdrian Kosowski, Dominik Pajak and Przemysław Uznański. Bounds on the Cover Time of Parallel Rotor Walks
Martin Huschenbett and Manfred KufleitnerEhrenfeucht-Fraisse Games on Omega-Terms
Marek Adamczyk, Maxim Sviridenko and Justin Ward. Submodular Stochastic Probing on Matroids
Moshe Lewenstein, Yakov Nekrich and Jeff VitterSpace-Efficient String Indexing for Wildcard Pattern Matching
Tomas Jelinek, Marcus Klaas and Guido Schaefer. Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players
Bruno BauwensAsymmetry of the Kolmogorov complexity of online predicting odd and even bits
Markus Lohrey and Georg ZetzscheOn Boolean closed full trios and rational Kripke frames
Adeline Pierrot and Dominique Rossin2-Stack Sorting is polynomial
John Mitchell and Joe Zimmerman. Data-Oblivious Data Structures
Online user: 1