List of accepted papers for STACS 2007:


Manindra Agrawal, Thanh Minh Hoang and Thomas Thierauf.
The polynomially bounded perfect matching problem is in NC^2 

Alberto Bertoni, Massimiliano Goldwurm and Violetta Lonati.
On the complexity of unary tiling-recognizable picture languages. 

Dietmar Berwanger.
Admissibility in infinite games 

Laurent Bienvenu.
Kolmogorov-Loveland stochasticity and Kolmogorov complexity 

Francine Blanchet-Sadri, Joshua Gafni and Kevin Wilson.
Correlations of Partial Words 

Hans Bodlaender.
A Cubic Kernel for Feedback Vertex Set 

Mikolaj Bojanczyk and Piotr Hoffman.
Reachability in Unions of Commutative Rewriting Systems is Decidable 

Felix Brandt, Felix Fischer and Markus Holzer.
Symmetries and the Complexity of Pure Nash Equilibrium 

Janina Brenner and Guido Schaefer.
Cost Sharing Methods for Makespan and Completion Time Scheduling 

Davide Bresolin, Angelo Montanari and Pietro Sala.
An optimal tableau-based decision algorithm for Propositional Neighborhood Logic 

Peter Buergisser.
On defining integers in the counting hierarchy and proving arithmetic circuit lower bounds 

Sergiu Bursuc, Hubert Comon and Stephanie Delaune.
Associative-Commutative Deducibility Constraints 

Costas Busch and Srikanta Tirthapura.
A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window 

Jin-Yi Cai and Pinyan Lu.
On Symmetric Signatures in Holographic Algorithms 

Ioannis Caragiannis.
Wavelength management in WDM rings to maximize the number of connections 

Olivier Carton, Jean Berstel, Luc Boasson and Isabelle Fagnot.
A First Investigation of Sturmian trees 

Arkadev Chattopadhyay, Andreas Krebs, Michal Koucky, Mario Szegedy, Pascal Tesson and Denis Therien.
Languages with bounded multiparty communication complexity 

Andrew Childs, Aram Harrow and Pawel Wocjan.
Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem 

Amin Coja-Oghlan, Michael Krivelevich and Danny Vilenchik.
Almost all k-colorable graphs are easy 

Bruno Courcelle and Andrew Twigg.
Compact Forbidden-set Routing 

Artur Czumaj and Christian Sohler.
Small Space Representations for Metric Min-Sum k-Clustering and their Applications 

Peter Damaschke.
The Union of Minimal Hitting Sets: Parameterized Combinatorial Bounds and Counting 

Benjamin Doerr.
Randomly Rounding Rationals with Cardinality Constraints and Derandomizations 

Adrian Dumitrescu and Csaba Toth.
Light Orthogonal Networks with Constant Geometric Dilation 

Robert Elsässer and Thomas Sauerwald.
Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs 

Javier Esparza, Stefan Kiefer and Michael Luttenberger.
On Fixed Point Equations over Commutative Semirings 

Eldar Fischer and Orly Yahalom.
Testing Convexity Properties of Tree Colorings 

Enrico Formenti and Petr Kurka.
A search algorithm for the maximal attractor of a cellular automaton 

Iftah Gamzu and Danny Segev.
Improved Online Algorithms for the Sorting Buffer Problem 

Hugo Gimbert.
Pure stationary optimal strategies in Markov decision processes 

Christian Glaßer, Alan L. Selman, Stephen Travers and Klaus W. Wagner.
The Complexity of Unions of Disjoint Sets 

Iman Hajirasouliha, Hossein Jowhari, Ravi Kumar and Ravi Sundaram.
On Completing Latin Squares 

Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond and Shigeru Yamashita.
Quantum Network Coding 

Pinar Heggernes, Karol Suchan, Ioan Todinca and Yngve Villanger.
Characterizing minimal interval completions: Towards better understanding of profile and pathwidth 

Chien-Chung Huang.
Cheating to Get Better Roommates in a Random Stable Matching 

Christian Hundt and Maciej Liskiewicz.
On the Complexity of Affine Image Matching 

Gábor Ivanyos, Miklos Santha and Luc Sanselme.
An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups. 

Telikepalli Kavitha, Kurt Mehlhorn and Dimitrios Michail.
New Approximation Algorithms for Minimum Cycle Bases of Graphs 

Pascal Koiran and Sylvain Perifel.
VPSPACE and a transfer theorem over the reals 

Daniel Kral.
Computing representations of matroids of bounded branch-width 

Ralf Kuesters and Tomasz Truderung.
On the Automatic Analysis of Recursive Security Protocols with XOR 

Manfred Kunde.
A new bound for pure greedy hot potato routing 

Gregory Lafitte and Michael Weiss.
Universal Tilings 

Soeren Laue and Stefan Funke.
Bounded-hop energy-efficient Broadcast in low-dimensional Metrics via Coresets 

Troy Lee.
A new rank technique for formula size lower bounds 

Nutan Limaye, Meena Mahajan and Raghavendra Rao.
Arithmetizing Classes arround NC1 and L 

Sylvain Lombardy.
On the Size of the Universal Automaton of a Regular Language 

Ilan Newman and Yuri Rabinovich.
Hard Metrics from Cayley Graphs of Abelian Groups 

Jan Poland.
On the Consistency of Discrete Bayesian Learning 

Andrea Sattler-Klein.
An Exponential Lower Bound For Prefix Gröbner Bases in Free Monoid Rings 

Henning Schnoor and Ilka Schnoor.
Enumerating all Solutions for Constraint Satisfaction Problems 

Lutz Schröder and Dirk Pattinson.
Rank-1 Modal Logics are Coalgebraic 

Thomas Schwentick and Volker Weber.
Bounded-Variable Fragments of Hybrid Logics 

Hans Ulrich Simon.
A Characterization of Strong Learnability in the Statistical Query Model 

Marc Tedder and Derek Corneil.
An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs 

Oleg Verbitsky.
Planar graphs: Logical complexity and parallel isomorphism tests