This book constitutes the refereed proceedings of the 14th International Symposium Fundamentals of Computation Theory, FCT 2003, held in Malm?, Sweden in August 2003.
The 36 revised full papers presented together with an invited paper and the abstracts of 2 invited talks were carefully reviewed and selected from 73 submissions. The papers are organized in topical sections on approximibility, algorithms, networks and complexity, computational biology, computational geometry, computational models and complexity, structural complexity, formal languages, and logic.
Author(s): Sanjeev Arora (auth.), Andrzej Lingas, Bengt J. Nilsson (eds.)
Series: Lecture Notes in Computer Science 2751
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2003
Language: English
Pages: 440
Tags: Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Mathematical Logic and Formal Languages; Discrete Mathematics in Computer Science; Computer Graphics
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 -
