STACS A

60 papers

YearTitle / Authors
20142-Stack Sorting is polynomial.
Adeline Pierrot, Dominique Rossin
201431st International Symposium on Theoretical Aspects of Computer Science, STACS 2014, Lyon, France, March 5-8, 2014
Ernst W. Mayr, Natacha Portier
2014A Solution to Wiehagen's Thesis.
Timo Kötzing
2014A glimpse on constant delay enumeration (Invited Talk).
Luc Segoufin
2014An optimal quantum algorithm for the oracle identification problem.
Robin Kothari
2014Approximation of smallest linear tree grammar.
Artur Jez, Markus Lohrey
2014Arithmetic Circuit Complexity (Tutorial).
Neeraj Kayal
2014Asymmetry of the Kolmogorov complexity of online predicting odd and even bits.
Bruno Bauwens
2014Balls into bins via local search: cover time and maximum load.
Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun
2014Bounds on the Cover Time of Parallel Rotor Walks.
Dariusz Dereniowski, Adrian Kosowski, Dominik Pajak, Przemyslaw Uznanski
2014Chordal Editing is Fixed-Parameter Tractable.
Yixin Cao, Dániel Marx
2014Coloring 3-colorable graphs with o(n^{1/5}) colors.
Ken-ichi Kawarabayashi, Mikkel Thorup
2014Communication Lower Bounds for Distributed-Memory Computations.
Michele Scquizzato, Francesco Silvestri
2014Complexity classes on spatially periodic Cellular Automata.
Nicolas Bacquey
2014Computability of the entropy of one-tape Turing machines.
Emmanuel Jeandel
2014Computational Complexity of the Extended Minimum Cost Homomorphism Problem on Three-Element Domains.
Hannes Uppman
2014Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players.
Tomas Jelinek, Marcus Klaas, Guido Schäfer
2014Constant Factor Approximation for Capacitated k-Center with Outliers.
Marek Cygan, Tomasz Kociumaka
2014Counting Homomorphisms to Cactus Graphs Modulo 2.
Andreas Göbel, Leslie Ann Goldberg, David Richerby
2014Data-Oblivious Data Structures.
John C. Mitchell, Joe Zimmerman
2014Depth-4 Lower Bounds, Determinantal Complexity: A Unified Approach.
Suryajith Chillara, Partha Mukhopadhyay
2014Differentiability of polynomial time computable functions.
André Nies
2014Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules.
Antonios Antoniadis, Neal Barcelo, Mario E. Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, Michele Scquizzato
2014Ehrenfeucht-Fraïssé Games on Omega-Terms.
Martin Huschenbett, Manfred Kufleitner
2014Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
Dániel Marx, Michal Pilipczuk
2014Explicit Linear Kernels via Dynamic Programming.
Valentin Garnero, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos
2014Exploring Subexponential Parameterized Complexity of Completion Problems.
Pål Grønås Drange, Fedor V. Fomin, Michal Pilipczuk, Yngve Villanger
2014Faster Compact On-Line Lempel-Ziv Factorization.
Jun-ichi Yamamoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda
2014Faster Sparse Suffix Sorting.
Tomohiro I, Juha Kärkkäinen, Dominik Kempa
2014From Small Space to Small Width in Resolution.
Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals
2014Frontmatter, Table of Contents, Preface, Conference Organization.
2014Generalized Reordering Buffer Management.
Yossi Azar, Matthias Englert, Iftah Gamzu, Eytan Kidron
2014Generalized Wong sequences and their applications to Edmonds' problems.
Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
2014Higher randomness and forcing with closed sets.
Benoit Monin
2014Irreversible computable functions.
Mathieu Hoyrup
2014Keeping a Crowd Safe: On the Complexity of Parameterized Verification (Invited Talk).
Javier Esparza
2014Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games.
Véronique Bruyère, Emmanuel Filiot, Mickael Randour, Jean-François Raskin
2014Near-Optimal Generalisations of a Theorem of Macbeath.
Nabil H. Mustafa, Saurabh Ray
2014New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings.
Francine Blanchet-Sadri, Michelle Bodnar, Benjamin De Winkle
2014Non-autoreducible Sets for NEXP.
Dung T. Nguyen, Alan L. Selman
2014On Boolean closed full trios and rational Kripke frames.
Markus Lohrey, Georg Zetzsche
2014On Symmetric Circuits and Fixed-Point Logics.
Matthew Anderson, Anuj Dawar
2014Online Bin Packing with Advice.
Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz
2014Online Dynamic Power Management with Hard Real-Time Guarantees.
Jian-Jia Chen, Mong-Jen Kao, D. T. Lee, Ignaz Rutter, Dorothea Wagner
2014Packing a Knapsack of Unknown Capacity.
Yann Disser, Max Klimm, Nicole Megow, Sebastian Stiller
2014Palindrome Recognition In The Streaming Model.
Petra Berenbrink, Funda Ergün, Frederik Mallmann-Trenn, Erfan Sadeqi Azer
2014Partition Expanders.
Dmitry Gavinsky, Pavel Pudlák
2014Randomized Online Algorithms with High Probability Guarantees.
Dennis Komm, Rastislav Královic, Richard Královic, Tobias Mömke
2014Read-Once Branching Programs for Tree Evaluation Problems.
Kazuo Iwama, Atsuki Nagao
2014Semi-algebraic geometry in computational game theory - a consumer's perspective (Invited Talk).
Peter Bro Miltersen
2014Shapley meets Shapley.
Haris Aziz, Bart de Keijzer
2014Space-Efficient String Indexing for Wildcard Pattern Matching.
Moshe Lewenstein, Yakov Nekrich, Jeffrey Scott Vitter
2014Stochastic Scheduling on Unrelated Machines.
Martin Skutella, Maxim Sviridenko, Marc Uetz
2014Submodular Stochastic Probing on Matroids.
Marek Adamczyk, Maxim Sviridenko, Justin Ward
2014Synchronizing Relations on Words.
Diego Figueira, Leonid Libkin
2014Testing Generalised Freeness of Words.
Pawel Gawrychowski, Florin Manea, Dirk Nowotka
2014The Complexity of Deciding Statistical Properties of Samplable Distributions.
Thomas Watson
2014Throughput Maximization in the Speed-Scaling Setting.
Eric Angel, Evripidis Bampis, Vincent Chau
2014Two-Page Book Embeddings of 4-Planar Graphs.
Michael A. Bekos, Martin Gronemann, Chrysanthi N. Raftopoulou
2014Weighted Coloring in Trees.
Júlio Araújo, Nicolas Nisse, Stéphane Pérennes