Fundamentals of Computation Theory: 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003. Proceedings

Front Matter....Pages -
Proving Integrality Gaps without Knowing the Linear Program....Pages 1-1
An Improved Analysis of Goemans and Williamson’s LP-Relaxation for MAX SAT....Pages 2-14
Certifying Unsatisfiability of Random 2 k -SAT Formulas Using Approximation Techniques....Pages 15-26
Inapproximability Results for Bounded Variants of Optimization Problems....Pages 27-38
Approximating the Pareto Curve with Local Search for the Bicriteria TSP(1,2) Problem....Pages 39-48
Scheduling to Minimize Max Flow Time: Offline and Online Algorithms....Pages 49-60
Linear Time Algorithms for Some NP-Complete Problems on ( P 5 ,Gem)-Free Graphs....Pages 61-72
Graph Searching, Elimination Trees, and a Generalization of Bandwidth....Pages 73-85
Constructing Sparse t -Spanners with Small Separators....Pages 86-97
Composing Equipotent Teams....Pages 98-108
Efficient Algorithms for GCD and Cubic Residuosity in the Ring of Eisenstein Integers....Pages 109-117
An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates....Pages 118-131
Periodic Multisorting Comparator Networks....Pages 132-143
Fast Periodic Correction Networks....Pages 144-156
Games and Networks....Pages 157-157
One-Way Communication Complexity of Symmetric Boolean Functions....Pages 158-170
Circuits on Cylinders....Pages 171-182
Fast Perfect Phylogeny Haplotype Inference....Pages 183-194
On Exact and Approximation Algorithms for Distinguishing Substring Selection....Pages 195-209
Complexity of Approximating Closest Substring Problems....Pages 210-221
On Lawson’s Oriented Walk in Random Delaunay Triangulations....Pages 222-233
Competitive Exploration of Rectilinear Polygons....Pages 234-245
An Improved Approximation Algorithm for Computing Geometric Shortest Paths....Pages 246-257
Adaptive and Compact Discretization for Weighted Region Optimal Path Finding....Pages 258-270
On Boundaries of Highly Visible Spaces and Applications....Pages 271-283
Membrane Computing....Pages 284-295
Classical Simulation Complexity of Quantum Machines....Pages 296-302
Using Depth to Capture Average-Case Complexity....Pages 303-310
Non-uniform Depth of Polynomial Time and Space Simulations....Pages 311-320
Dimension- and Time-Hierarchies for Small Time Bounds....Pages 321-332
Baire’s Categories on Small Complexity Classes....Pages 333-342
Operations Preserving Recognizable Languages....Pages 343-354
Languages Defined by Generalized Equality Sets....Pages 355-363
Context-Sensitive Equivalences for Non-interference Based Protocol Analysis....Pages 364-375
On the Exponentiation of Languages....Pages 376-386
Kleene’s Theorem for Weighted Tree-Automata....Pages 387-399
Weak Cardinality Theorems for First-Order Logic....Pages 400-411
Compositionality of Hennessy-Milner Logic through Structural Operational Semantics....Pages 412-422
On a Logical Approach to Estimating Computational Complexity of Potentially Intractable Problems....Pages 423-431
Back Matter....Pages -