Martin Grohe, Christoph Koch, Nicole Schweikardt (auth.), Maciej Liśkiewicz, Rüdiger Reischuk (eds.)3540281932, 9783540281931
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.
Table of contents :
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 –
Reviews
There are no reviews yet.