Fundamentals of Computation Theory

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Proving Integrality Gaps without Knowing the Linear Program
3. Altmetric Badge
   Chapter 2 An Improved Analysis of Goemans and Williamson’s LP-Relaxation for MAX SAT
4. Altmetric Badge
   Chapter 3 Certifying Unsatisfiability of Random 2 k -SAT Formulas Using Approximation Techniques
5. Altmetric Badge
   Chapter 4 Inapproximability Results for Bounded Variants of Optimization Problems
6. Altmetric Badge
   Chapter 5 Approximating the Pareto Curve with Local Search for the Bicriteria TSP(1,2) Problem
7. Altmetric Badge
   Chapter 6 Scheduling to Minimize Max Flow Time: Offline and Online Algorithms
8. Altmetric Badge
   Chapter 7 Linear Time Algorithms for Some NP-Complete Problems on ( P 5 ,Gem)-Free Graphs
9. Altmetric Badge
   Chapter 8 Graph Searching, Elimination Trees, and a Generalization of Bandwidth
10. Altmetric Badge
    Chapter 9 Constructing Sparse t -Spanners with Small Separators
11. Altmetric Badge
    Chapter 10 Composing Equipotent Teams
12. Altmetric Badge
    Chapter 11 Efficient Algorithms for GCD and Cubic Residuosity in the Ring of Eisenstein Integers
13. Altmetric Badge
    Chapter 12 An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates
14. Altmetric Badge
    Chapter 13 Periodic Multisorting Comparator Networks
15. Altmetric Badge
    Chapter 14 Fast Periodic Correction Networks
16. Altmetric Badge
    Chapter 15 Games and Networks
17. Altmetric Badge
    Chapter 16 One-Way Communication Complexity of Symmetric Boolean Functions
18. Altmetric Badge
    Chapter 17 Circuits on Cylinders
19. Altmetric Badge
    Chapter 18 Fast Perfect Phylogeny Haplotype Inference
20. Altmetric Badge
    Chapter 19 On Exact and Approximation Algorithms for Distinguishing Substring Selection
21. Altmetric Badge
    Chapter 20 Complexity of Approximating Closest Substring Problems
22. Altmetric Badge
    Chapter 21 On Lawson’s Oriented Walk in Random Delaunay Triangulations
23. Altmetric Badge
    Chapter 22 Competitive Exploration of Rectilinear Polygons
24. Altmetric Badge
    Chapter 23 An Improved Approximation Algorithm for Computing Geometric Shortest Paths
25. Altmetric Badge
    Chapter 24 Adaptive and Compact Discretization for Weighted Region Optimal Path Finding
26. Altmetric Badge
    Chapter 25 On Boundaries of Highly Visible Spaces and Applications
27. Altmetric Badge
    Chapter 26 Membrane Computing
28. Altmetric Badge
    Chapter 27 Classical Simulation Complexity of Quantum Machines
29. Altmetric Badge
    Chapter 28 Using Depth to Capture Average-Case Complexity
30. Altmetric Badge
    Chapter 29 Non-uniform Depth of Polynomial Time and Space Simulations
31. Altmetric Badge
    Chapter 30 Dimension- and Time-Hierarchies for Small Time Bounds
32. Altmetric Badge
    Chapter 31 Baire’s Categories on Small Complexity Classes
33. Altmetric Badge
    Chapter 32 Operations Preserving Recognizable Languages
34. Altmetric Badge
    Chapter 33 Languages Defined by Generalized Equality Sets
35. Altmetric Badge
    Chapter 34 Context-Sensitive Equivalences for Non-interference Based Protocol Analysis
36. Altmetric Badge
    Chapter 35 On the Exponentiation of Languages
37. Altmetric Badge
    Chapter 36 Kleene’s Theorem for Weighted Tree-Automata
38. Altmetric Badge
    Chapter 37 Weak Cardinality Theorems for First-Order Logic
39. Altmetric Badge
    Chapter 38 Compositionality of Hennessy-Milner Logic through Structural Operational Semantics
40. Altmetric Badge
    Chapter 39 On a Logical Approach to Estimating Computational Complexity of Potentially Intractable Problems