List of accepted papers for STACS 2010:


Rustem Takhanov. 
Dichotomy theorem for general Minimum Cost Homomorphisms Problem

Dietrich Kuske. 
Is Ramsey's theorem omega-automatic?

Claire Mathieu, Ocan Sankur and Warren Schudy. 
Online Correlation Clustering

Maurice Jansen. 
Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion

Adrian Dumitrescu and Csaba Toth. 
Long non-crossing configurations in the plane

Shiri Chechik and David Peleg. 
Fault Tolerant uncapacitated facility location

Ryan Williams. 
Alternation-Trading Proofs, Linear Programming, and Lower Bounds

Adrian Dumitrescu and Minghui Jiang. 
Dispersion in unit disks

Jens M. Schmidt. 
Construction Sequences and Certifying 3-Connectedness

Laszlo Babai, Anandam Banerjee, Raghav Kulkarni and Vipul Naik. 
Evasiveness and the Distribution of Prime Numbers

Edward A. Hirsch and Dmitry Itsykson. 
On optimal heuristic randomized semidecision procedures, with application to proof complexity

Victor Chen, Elena Grigorescu and Ronald de Wolf. 
Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation

Daniel Marx, Barry O'Sullivan and Igor Razgon. 
Treewidth reduction for constrained separation and bipartization problems

Francois Le Gall. 
An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem

Nader Bshouty and Hanna Mazzawi. 
Optimal Query Complexity for Reconstructing Hypergraphs

Rafail Ostrovsky and Vladimir Braverman. 
AMS Without 4-Wise Independence on Product Domains

Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius and David Richerby. 
The Complexity of Approximating Bounded-Degree Boolean #CSP

Stefan Goller and Markus Lohrey. 
Branching-time model checking of one-counter processes

George Mertzios, Ignasi Sau and Shmuel Zaks. 
The Recognition of Tolerance and Bounded Tolerance Graphs

Leah Epstein, Asaf Levin, Julian Mestre and Danny Segev. 
Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model

Fedor Fomin and Yngve Villanger. 
Finding Induced Subgraphs via Minimal Triangulations

Liam Roditty and David Peleg. 
Relaxed spanners for directed disk graphs

Sourav Chakraborty, Eldar Fischer, Oded Lachish and Raphael Yuster. 
Two-phase algorithms for the parametric shortest path problem

H.L. Chan, T.W. Lam, L.K. Lee and H.F. Ting. 
Continuous Monitoring of Distributed Data Streams over a Time-based Sliding Window

Vikraman Arvind and Srikanth Srinivasan. 
The Remote Point Problem, Small Bias spaces, and Expanding Generator sets

Frederic Dorn, Fedor Fomin, Daniel Lokshtanov, Venkatesh Raman and Saket Saurabh. 
Beyond Bidimensionality:Parameterized Subexponential Algorithms on Directed Graphs

Bireswar Das, Jacobo Toran and Fabian Wagner. 
Restricted Space Algorithms for Isomorphism On Bounded Treewidth Graphs

Alexander Kartzow. 
Collapsible pushdown graphs of level 2 are tree-automatic

Andreas Bjorklund. 
Exact Covers via Determinants

Neelesh Khanna and Surender Baswana.
Approximate Shortest Path Oracle under Vertex Failure

Frederic Dorn. 
Planar Subgraph Isomorphism Revisited

Michal Adamaszek and Anna Adamaszek. 
Large-girth roots of graphs

Bireswar Das, Samir Datta and Prajakta Nimbhorkar. 
Log-space Algorithms for Paths and Matchings in k-trees

Paul Duetting, Monika Henzinger and Ingmar Weber. 
Sponsored Search, Market Equilibria, and the Hungarian Method

Pierre Guillon and Gaetan Richard. 
Revisiting the Rice Theorem of Cellular Automata

Dominik Scheder. 
Unsatisfiable Linear CNF Formulas Are Large and Complex

Angelo Montanari, Gabriele Puppis, Pietro Sala and Guido Sciavicco. 
Decidability of the interval temporal logic ABB over the natural numbers

Lutz Schroder and Dirk Pattinson. 
Named Models in Coalgebraic Hybrid Logic

David Doty, Jack Lutz, Matt Patitz, Scott Summers and Damien Woods. 
Intrinsic Universality in Self-Assembly

Laszlo Egri, Andrei Krokhin, Benoit Larose and Pascal Tesson. 
The complexity of the list homomorphism problem for graphs

Mark de Berg, Fred van Nijnatten, Rene Sitters, Gerhard Woeginger and Alexander Wolff. 
The Traveling Salesman Problem Under Squared Euclidean Distances

Julien Cervelle, Enrico Formenti and Pierre Guillon. 
Ultimate Traces of Cellular Automata

Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski and Dariusz Kowalski. 
Dynamic Sharing of a Multiple Access Channel

Javier Esparza, Andreas Gaiser and Stefan Kiefer. 
Computing Least Fixed Points of Probabilistic Systems of Polynomials

Jiri Fiala, Marcin Kaminski, Bernard Lidicky and Daniel Paulusma. 
The k-in-a-path problem for claw-free graphs

Sergey Bravyi, Aram Harrow and Avinatan Hassidim. 
Quantum algorithms for testing properties of distributions

Lukasz Jez. 
A 4/3-competitive randomised algorithm for online scheduling of packets with agreeable deadlines

Felix Brandt, Felix Fischer and Markus Holzer. 
On Iterated Dominance, Matrix Elimination, and Matched Paths

Michael Kowalczyk and Jin-Yi Cai. 
Holant Problems for Regular Graphs with Complex Edge Functions

Artur Jez and Alexander Okhotin. 
On equations over sets of integers

Serge Grigorieff and Pierre Valarcher. 
Local Evolving Algebras unify all kinds of sequential computation models

Xiaoyang Gu, John Hitchcock and A Pavan. 
Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses

Xavier Allamigeon, Stephane Gaubert and Eric Goubault. 
The tropical double description method

Lance Fortnow, Jack H. Lutz and Elvira Mayordomo. 
Inseparability and Strong Hypotheses for Disjoint NP Pairs