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: 2