Fundamentals of Computation Theory: 15th International Symposium, FCT 2005, Lübeck, Germany, August 17-20, 2005. Proceedings

Front Matter....Pages -
The Complexity of Querying External Memory and Streaming Data....Pages 1-16
The Smoothed Analysis of Algorithms....Pages 17-18
Path Coupling Using Stopping Times....Pages 19-31
On the Incompressibility of Monotone DNFs....Pages 32-43
Bounds on the Power of Constant-Depth Quantum Circuits....Pages 44-55
Biautomatic Semigroups....Pages 56-67
Deterministic Automata on Unranked Trees....Pages 68-79
Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals....Pages 80-91
Generic Density and Small Span Theorem....Pages 92-102
Logspace Optimization Problems and Their Approximability Properties....Pages 103-114
A Faster and Simpler 2-Approximation Algorithm for Block Sorting....Pages 115-124
On the Power of Unambiguity in Alternating Machines....Pages 125-136
Translational Lemmas for Alternating TMs and PRAMs....Pages 137-148
Collapsing Recursive Oracles for Relativized Polynomial Hierarchies....Pages 149-160
Exact Algorithms for Graph Homomorphisms....Pages 161-171
Improved Algorithms and Complexity Results for Power Domination in Graphs....Pages 172-184
Clique-Width for Four-Vertex Forbidden Subgraphs....Pages 185-196
On the Complexity of Uniformly Mixed Nash Equilibria and Related Regular Subgraph Problems....Pages 197-208
Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems....Pages 209-220
Perfect Reconstruction of Black Pixels Revisited....Pages 221-232
Adaptive Zooming in Point Set Labeling....Pages 233-244
On the Black-Box Complexity of Sperner’s Lemma....Pages 245-257
Property Testing and the Branching Program Size of Boolean Functions....Pages 258-269
Almost Optimal Explicit Selectors....Pages 270-280
The Delayed k -Server Problem....Pages 281-292
Leftist Grammars and the Chomsky Hierarchy....Pages 293-304
Shrinking Multi-pushdown Automata....Pages 305-316
A Simple and Fast Min-cut Algorithm....Pages 317-328
(Non)-Approximability for the Multi-criteria TSP (1,2)....Pages 329-340
Completeness and Compactness of Quantitative Domains....Pages 341-351
A Self-dependency Constraint in the Simply Typed Lambda Calculus....Pages 352-364
A Type System for Computationally Secure Information Flow....Pages 365-377
Algorithms for Graphs Embeddable with Few Crossings Per Edge....Pages 378-387
Approximation Results for the Weighted P 4 Partition Problems....Pages 388-396
The Maximum Resource Bin Packing Problem....Pages 397-408
Average-Case Non-approximability of Optimisation Problems....Pages 409-421
Relations Between Average-Case and Worst-Case Complexity....Pages 422-432
Reconstructing Many Partitions Using Spectral Techniques....Pages 433-444
Constant Time Generation of Linear Extensions....Pages 445-453
On Approximating Real-World Halting Problems....Pages 454-466
An Explicit Solution to Post’s Problem over the Reals....Pages 467-478
The Complexity of Semilinear Problems in Succinct Representation....Pages 479-490
On Finding Acyclic Subhypergraphs....Pages 491-503
An Improved Approximation Algorithm for TSP with Distances One and Two....Pages 504-515
New Applications of Clique Separator Decomposition for the Maximum Weight Stable Set Problem....Pages 516-527
On the Expressiveness of Asynchronous Cellular Automata....Pages 528-539
Tree Automata and Discrete Distributed Games....Pages 540-551
A New Linearizing Restriction in the Pattern Matching Problem....Pages 552-562
Fully Incremental LCS Computation....Pages 563-574
Back Matter....Pages -