STACS 2014: 31st Symposium on Theoretical Aspect of Computer Science

Programm

Thursday, March 6th

9.00 – 10.00 Invited Talk - Chair: Anca Muscholl - Organizing: Aurélie Lagoutte

• Javier Esparza, TUM - Technische Universität München, Keeping a Crowd Safe: On the Complexity of Parameterized Verification

10.20–11.35 Session 1A: Logic - Chair: Heribert Vollmer - Organizing: Maxime Senot

• Matthew Anderson and Anuj Dawar. On Symmetric Circuits and Fixed-Point Logics

• Markus Lohrey and Georg Zetzsche. On Boolean closed full trios and rational Kripke frames

• Martin Huschenbett and Manfred Kufleitner. Ehrenfeucht-Fraisse Games on Omega-Terms

10.20–11.35 Session 1B:  Graphs - Chair: Stephan Thomassé   -  Organizing: Théophile Trunck

• Ken-Ichi Kawarabayashi and Mikkel Thorup. Coloring 3-colorable graphs with o(n^{1/5}) colors

• Dmitry Gavinsky and Pavel Pudlák. Partition Expanders

• Julio Araujo, Nicolas Nisse and Stéphane Pérennes. Weighted Coloring in Trees

11.50–12.40 Session 2A:  Complexity - Chair: Luc Ségoufin   -  Organizing: Timothée Pécatte

• Robin Kothari. An optimal quantum algorithm for the oracle identification problem

• Dániel Marx and Michał Pilipczuk. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)

11.50–12.40 Session 2B:  Automata - Chair: Nathalie Aubrun  -  Organizing: Maxime Senot

• Nicolas Bacquey. Complexity classes on spatially periodic Cellular Automata

• Diego Figueira and Leonid Libkin. Synchronizing Relations on Words

LUNCH

14.30–15.45 Session 3A: Scheduling -  Chair: Loris Marchal   -  Organizing: Guillaume Aupy

• Eric Angel, Evripidis Bampis and Vincent Chau. Throughput Maximization in the Speed-Scaling Setting

• Martin Skutella, Maxim Sviridenko and Marc Uetz. Stochastic Scheduling on Unrelated Machines

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

14.30–15.45 Session 3B: Graphs  -  Chair: Christophe Paul   -  Organizing: Matthieu Rosenfeld

• Andreas Göbel, Leslie Ann Goldberg and David Richerby. Counting Homomorphisms to Cactus Graphs Modulo 2

• Michael A. Bekos, Martin Gronemann and Chrysanthi N. Raftopoulou. Two-Page Book Embeddings of 4-Planar Graphs

• Dariusz Dereniowski, Adrian Kosowski, Dominik Pająk and Przemysław Uznański. Bounds on the Cover Time of Parallel Rotor Walks

16.00–17.15 Session 4A: Game Theory  -  Chair: Laurent Doyen   -  Organizing: Aurélie Lagoutte

• Haris Aziz and Bart de Keijzer. Shapley Meets Shapley

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

• Tomas Jelinek, Marcus Klaas and Guido Schäfer. Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players

16.00–17.15 Session 4B: Words  -  Chair: Michael Rao  -   Organizing: Matthieu Rosenfeld

• Tomohiro I, Juha Kärkkäinen and Dominik Kempa. Faster Sparse Suffix Sorting

• Pawel Gawrychowski, Florin Manea and Dirk Nowotka. Testing Generalised Freeness of Words

• Francine Blanchet-Sadri, Michelle Bodnar and Benjamin De Winkle. New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate String

Visit of the city

Friday, March 7th

9.00–10.15 Session 5A: Algorithms  -  Chair: Thomas Schwentick  -   Organizing: Petru Valicov

• Yann Disser, Max Klimm, Nicole Megow and Sebastian Stiller. Packing a Knapsack of Unknown Capacity

• Nabil H. Mustafa and Saurabh Ray. Near-Optimal Generalisations of a Theorem of Macbeath

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

9.00–10.15 Session 5B: Fixed Parameter Tractability  -  Chair: Eric Thierry   -  Organizing: Sébastien Tavenas

• Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk and Yngve Villanger. Exploring Subexponential Parameterized Complexity of Completion Problems

• Valentin Garnero, Christophe Paul, Ignasi Sau and Dimitrios M. Thilikos. Explicit Linear Kernels via Dynamic Programming

• Yixin Cao and Dániel Marx. Chordal Editing is Fixed-Parameter Tractable

10.30–11.20 Session 6A: Words  -  Chair: Michael Rao  -   Organizing: Petru Valicov

• Moshe Lewenstein, Yakov Nekrich and Jeffrey Scott Vitter. Space-Efficient String Indexing for Wildcard Pattern Matching

• Artur Jeż and Markus Lohrey. Approximation of smallest linear tree grammar

10.30–11.20 Session 6B: Algebraic Complexity  -  Chair: Neeraj Kayal   -  Organizing: Sébastien Tavenas

• Suryajith Chillara and Partha Mukhopadhyay. Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach

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

11.40–12.40 Invited Talk  -  Chair: Marie-Pierre Béal   -  Organizing: Aurélie Lagoutte

• Luc Segoufin, INRIA, École Normale Supérieure de Cachan
  A glimpse on constant delay enumeration

LUNCH

14.30–15.45 Session 7A: Algorithms  -  Chair: Markus Lohrey  -  Organizing: Théophile Trunck

• Marek Cygan and Tomasz Kociumaka. Constant Factor Approximation for Capacitated k-Center with Outliers

• Marek Adamczyk, Maxim Sviridenko and Justin Ward. Submodular Stochastic Probing on Matroids

• John C. Mitchell and Joe Zimmerman. Data-Oblivious Data Structures

14.30–15.45 Session 7B: Computability -  Chair: Peter Bro Miltersen   -  Organizing: Maxime Senot

• Benoit Monin. Higher randomness and forcing with closed sets

• Bruno Bauwens. Asymmetry of the Kolmogorov complexity of online predicting odd and even bits

• Timo Kötzing. A Solution to Wiehagen's Thesis

16.00–17.15 Session 8A: Online Algorithms  -  Chair: Adi Rosen   -  Organizing: Gauillaume Aupy

• Yossi Azar, Matthias Englert, Iftah Gamzu and Eytan Kidron. Generalized Reordering Buffer Management

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

• Dennis Komm, Rastislav Královič, Richard Královič and Tobias Mömke. Randomized Online Algorithms with High Probability Guarantees

16.00–17.15 Session 8B: Computability  -  Chair: Nicolas Ollinger  -   Organizing: Maxime Senot

• Mathieu Hoyrup. Irreversible computable functions

• André Nies. Differentiability of polynomial time computable functions

• Emmanuel Jeandel. Computability of the entropy of one-tape Turing Machines

Conference dinner

Saturday, March 8th

9.00–10.15 Session 9A: Online Algorithms  -  Chair: Pablo Arrighi  -  Organizing: Guillaume Aupy

• Jun’ichi Yamamoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda. Faster Compact On-Line Lempel-Ziv Factorization

• Petra Berenbrink, Funda Ergün, Frederik Mallmann-Trenn and Erfan Sadeqi Azer. Palindrome Recognition In The Streaming Model

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

9.00–10.15 Session 9B: Complexity   -  Chair: Ernst Mayr  -   Organizing: William Lochet

• Dung T. Nguyen and Alan L. Selman. Non-autoreducible sets for NEXP

• Hannes Uppman. Computational Complexity of the Minimum Cost Homomorphism Problem on Three-Element Domains

• Thomas Watson. The Complexity of Deciding Statistical Properties of Samplable Distributions

10.30–11.20 Session 10A: Algorithms and Communication Lower Bounds  -  Chair: Ernst Mayr  -  Organizing: Aurélie Lagoutte

• Adeline Pierrot and Dominique Rossin. 2-Stack Sorting is polynomial

• Michele Scquizzato and Francesco Silvestri. Communication Lower Bounds for Distributed-Memory Computations

10.30–11.20 Session 10B: Complexity  -  Chair: Marius Zimand   -   Organizing:  William Lochet

• Kazuo Iwama and Atsuki Nagao. Read-Once Branching Programs for Tree Evaluation Problems

• Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström and Marc Vinyals. From Small Space to Small Width in Resolution

11.40–12.40 Invited Talk  -  Chair: Martin Dietzfelbinger   -  Organizing: Aurélie Lagoutte

• Peter Bro Miltersen, Aarhus University
  Semi-algebraic geometry in computational game theory - a consumer's perspective