Algorithms and Complexity

Front Cover

Algorithms and Complexity

Copyright Page

Table of Contents

Preface

List of Contributors to Volume A

CHAPTER 1. Machine Models and Simulations

1. Introduction

2. Sequential machine models

3. The second machine class

4. Parallel machine models outside the second machine class

Acknowledgment

References

CHAPTER 2. A Catalog of Complexity Classes

1. Preliminaries

2. Presumably intractable problems

3. Provably intractable problems

4. Classes that count

5. Inside P

6. New developments, tables and figures

References

CHAPTER 3. Machine-Independent Complexity Theory

1. Introduction

2. Simple Turing machines and space complexity

3. Recursion, padding and compression

4. Gaps and arbitrary speed-up

5. Effective speed-up

6. Fundamental Theorem for STM space

7. Machine independence

Acknowledgment

References

CHAPTER 4. Kolmogorov Complexity and its Applications

1. Introduction

2. Mathematical theory

3. Applications of compressibility

4. Example of an application in mathematics: weak prime number theorems

5. Applications of incompressibility: proving lower bounds

6. Resource-bounded Kolmogorov complexity and its applications

7. Conclusion

Acknowledgment

References

CHAPTER 5. Algorithms for Finding Patterns in Strings

1. Introduction

2. Notations for patterns

3. Matching keywords

4. Matching sets of keywords

5. Matching regular expressions

6. Related problems

7. Concluding remarks

Acknowledgment

References

CHAPTER 6. Data Structures

1. Introduction

2. The dictionary problem

3. The weighted dictionary problem and self-organizing data structures

4. Persistence

5. The Union-Split-Find problem

6. Priority queues

7. Nearest common ancestors

8. Selection

9. Merging

10. Dynamization techniques

References

CHAPTER 7. Computational Geometry

1. Introduction

2. Techniques and paradigms

3. Convex hulls

4. Voronoi diagrams

5. Proximity problems

6. Linear programming

7. Triangulation and decomposition

8. Planar point location

9. Multidimensional trees

10. Range search

11. Visibility computations

12. Combinatorial geometry

13. Other topics

14. Conclusion

References

CHAPTER 8. Algorithmic Motion Planning in Robotics

1. Introduction

2. Statement of the problem

3. Motion planning in static and known environments

4. Variants of the motion planning problem

5. Results in computational geometry relevant to motion planning

Acknowledgment

References

CHAPTER 9. Average-Case Analysis of Algorithms and Data Structures

0. Introduction

1. Combinatorial enumerations

2. Asymptotic methods

3. Sorting algorithms

4. Recursive decompositions and algorithms on trees

5. Hashing and address computation techniques

6. Dynamic algorithms

Acknowledgment

References

CHAPTER 10. Graph Algorithms

Prelude

1. Representation of graphs

2. Basic structure algorithms

3. Combinatorial optimization on graphs

References

CHAPTER 11. Algebraic Complexity Theory

1. Introduction

2. Addition chains

3. Computation sequences

4. Substitution

5. Degree of transcendency

6. Geometric degree

7. Derivatives

8. Branching

9. Complexity classes

10. Matrix multiplication and bilinear complexity

11. Degeneration and asymptotic spectrum

12. Lower bounds for rank and border rank

13. Fourier transform

14. Complete problems

15. Conclusion

References

CHAPTER 12. Algorithms in Number Theory

1. Introduction

2. Preliminaries

3. Algorithms for finite abelian groups

4. Factoring integers

5. Primality testing

Acknowledgment

References

CHAPTER 13. Cryptography

1. Introduction

2. Basics

3. The goals and tools of cryptology

4. Mathematical preliminaries

5. Complexity-theoretic foundations of cryptography

6. Privacy

7. Generating random or pseudo-random sequences and functions

8. Digital signatures

9. Two-party protocols

10. Multi-party protocols

11. Cryptography and complexity theory

Acknowledgment

References

CHAPTER 14. The Complexity of Finite Functions

1. Introduction

2. General circuits

3. Bounded-depth circuits

4. Monotone circuits

5. Formulas

6. Branching programs

7. Conclusion

Acknowledgment

References

CHAPTER 15. Communication Networks

1. Introduction

2. Communication problems

3. The Ajtai, Komlós and Szemerédi Theorem

Acknowledgment

References

CHAPTER 16. VLSI Theory

1. Introduction

2. VLSI complexity measures

3. The VLSI model

4. The basic lower bound argument

5. A geometric separator theorem

6. The communication complexity of Boolean predicates

7. The communication complexity of Boolean functions with many outputs

8. A lower bound on the switching energy of VLSI chips

9. Upper bounds on the AT2 -complexity of VLSI chips

Acknowledgment

References

CHAPTER 17. Parallel Algorithmsfor Shared-Memory Machines

1. Introduction

2. Efficient PRAM algorithms

3. Models of parallel computation

4. NC-algorithms and P-complete problems

5. Conclusion

Acknowledgment

References

CHAPTER 18. General Purpose Parallel Architectures

1. Introduction

2. Some networks

3. Routing

4. Universality

Acknowledgment

References

Subject Index