Portal - STACS 2014

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

Blanchet-Sadri, Francine

Kawarabayashi, Ken-ichi

López-Ortiz, Alejandro

Mallmann-Trenn, Frederik

Raftopoulou, Chrysanthi N.

Randour, Mickael

Raskin, Jean-François

Thilikos, Dimitrios M.

Vitter, Jeffrey Scott

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 | Privacy Published by LZI

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