STACS 2004: 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004. Proceedings

Front Matter....Pages -
Approximation Schemes for Metric Clustering Problems....Pages 1-3
Positional Determinacy of Infinite Games....Pages 4-18
Individual Communication Complexity....Pages 19-30
The Complexity of Satisfiability Problems over Finite Lattices....Pages 31-43
Constant Width Planar Computation Characterizes ACC 0 ....Pages 44-55
A Simple and Fast Approach for Solving Problems on Planar Graphs....Pages 56-67
Sum-Multicoloring on Paths....Pages 68-80
Matching Algorithms Are Fast in Sparse Random Graphs....Pages 81-92
Algebraic Results on Quantum Automata....Pages 93-104
Quantum Identification of Boolean Oracles....Pages 105-116
Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models....Pages 117-128
A Discontinuity in Pattern Inference....Pages 129-140
Algorithms for SAT Based on Search in Hamming Balls....Pages 141-151
Identifying Efficiently Solvable Cases of Max CSP....Pages 152-163
The Complexity of Boolean Constraint Isomorphism....Pages 164-175
On Minimizing the Total Weighted Tardiness on a Single Machine....Pages 176-186
Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs....Pages 187-198
Optimal and Online Preemptive Scheduling on Uniformly Related Machines....Pages 199-210
Parallel Prefetching and Caching Is Hard....Pages 211-221
Strongly Stable Matchings in Time O ( nm ) and Extension to the Hospitals-Residents Problem....Pages 222-233
Approximation Algorithms for Minimizing Average Distortion....Pages 234-245
Digraphs Exploration with Little Memory....Pages 246-257
Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks....Pages 258-269
An Algorithmic View on OVSF Code Assignment....Pages 270-281
The Syntactic Graph of a Sofic Shift....Pages 282-293
Periodicity and Unbordered Words....Pages 294-304
Desert Automata and the Finite Substitution Problem....Pages 305-316
Satisfiability Problems Complete for Deterministic Logarithmic Space....Pages 317-325
A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number....Pages 326-337
The Minimal Logically-Defined NP-Complete Problem....Pages 338-349
Solving the 2-Disjoint Paths Problem in Nearly Linear Time....Pages 350-361
Simpler Computation of Single-Source Shortest Paths in Linear Average Time....Pages 362-369
Lattices with Many Cycles Are Dense....Pages 370-381
Automata-Based Analysis of Recursive Cryptographic Protocols....Pages 382-393
On Minimum Circular Arrangement....Pages 394-405
Integral Symmetric 2-Commodity Flows....Pages 406-417
Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks....Pages 418-427
On the Expressiveness of Deterministic Transducers over Infinite Trees....Pages 428-439
Definability and Regularity in Automatic Structures....Pages 440-451
Active Context-Free Games....Pages 452-464
Worst Case Performance of an Approximation Algorithm for Asymmetric TSP....Pages 465-476
On Visibility Representation of Plane Graphs....Pages 477-488
Topology Matters: Smoothed Competitiveness of Metrical Task Systems....Pages 489-500
A Randomized Competitive Algorithm for Evaluating Priced AND/OR Trees....Pages 501-512
The Plurality Problem with Three Colors....Pages 513-521
A Measured Collapse of the Modal μ -Calculus Alternation Hierarchy....Pages 522-533
An Information Theoretic Lower Bound for Broadcasting in Radio Networks....Pages 534-546
A New Model for Selfish Routing....Pages 547-558
Broadcast in the Rendezvous Model....Pages 559-570
Time-Space Tradeoff in Derandomizing Probabilistic Logspace....Pages 571-583
What Can be Efficiently Reduced to the K-Random Strings?....Pages 584-595
Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints between Regular Open Terms....Pages 596-607
Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines....Pages 608-619
The Expected Competitive Ratio for Weighted Completion Time Scheduling....Pages 620-631
Effective Strong Dimension in Algorithmic Information and Computational Complexity....Pages 632-643
A Lower Bound on the Competitive Ratio of Truthful Auctions....Pages 644-655
Errata to Analysis of the Harmonic Algorithm for Three Servers....Pages 656-656
Back Matter....Pages -