This book constitutes the refereed proceedings of the 15th International Symposium Fundamentals of Computation Theory, FCT 2005, held in Lübeck, Germany in August 2005.
　　The 46 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 105 submissions. The papers are organized in topical sections on circuits, automata, complexity, approximability, computational and structural complexity, graphs and complexity, computational game theory, visual cryptography and computational geometry, query complexity, distributed systems, automata and formal languages, semantics, approximation algorithms, average case complexity, algorithms, graph algorithms, and pattern matching.Invited Talks
　The Complexity of Querying External Memory and Streaming Data
　The Smoothed Analysis of Algorithms
Path Coupling Using Stopping Times
Circuits
On the Incompressibility of Monotone DNFs
Bounds on the Power of Constant-Depth Quantum Circuits
Automata I
Biautomatic Semigroups
Deterministic Automata on Unranked Trees
Complexity I
Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals
Generic Densitv and Small Span Theorem
Approximability
Logspace Optimization Problems and Their Approximability Properties
A Faster and Simpler 2-Approximation Algorithm for Block Sorting
Computational and Structural Complexity
On the Power of Unambiguity in Alternating Machines
Translational Lemmas for Alternating TMs and PRAMs
Collapsing Recursive Oracles for Relativized Polynomial Hierarchies
Graphs and Complexity
Exact Algorithms for Graph Homomorphisms
Improved Algorithms and Complexity Results for Power Domination in Graphs
Clique-Width for Four-Vertex Forbidden Subgraphs
Computational Game Theory
On the Complexity of Uniformly Mixed Nash Equilibria and RelatedRegular Subgraph Problems
Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems
Visual Cryptography and Computational Geometry
Perfect Reconstruction of Black Pixels Revisited
Adaptive Zooming in Point Set Labeling
Query Complexity
Graph Algorithms
Approximation Algorithms
Average-Case Compexity
Algorithms
ComplexityⅡ
Graph Algorithms
AutomataⅡ
Pattern Matching
Author Index