Complexity of Algorithms

(Topic outline)

1. Models of computation

1.1 Finite automata
1.2 Turing machines
1.3 Random Access Machines
1.4 Boolean functions and circuits
1.5 Clocked circuits
1.6 Cellular automata
Exercises

2. The power of machines: algorithmic decidability

2.1 Regular languages
2.2 Recursive and recursively enumerable languages
2.3 Other algorithmically undecidable problems
2.4 Logically undecidable problems
Exercises

3. Computation with resource bounds

3.1 Time and space
3.2 Polynomial time I: Arithmetic
3.3 Polynomial time II: Graph Theory
3.4 Polynomial space: games
3.5 Other important complexity classes
Exercises

4. Time and space: general complexity theory

Exercises

5. Non-deterministic algorithms

5.1 Non-deterministic Turing machines
5.2 The complexity of non-deterministic algorithms
5.3 Languages in NP
5.4 NP-completeness
5.5 Other NP-complete problems
Exercises

6. Randomization

6.1 Verifying a polynomial identity
6.2 Prime testing
6.2 Randomized complexity classes
Exercises

7. Information complexity

7.1 Infomation (Kolmogorov) complexity
7.2 Self-limiting information complexity
7.3 The notion of a random sequence
7.4 Kolmogorov complexity and data compression
Exercises

8. Pseudo-random numbers

8.1 Classical methods
8.2 Pseudo-random numbers
8.3 One-way functions
Exercises

9. Parallel algorithms

8.1 Parallel random access machines
8.2 The class NC
Exercises

10. Decision trees

9.1 Algorithms decision trees: sorting and searching
9.2 Non-deterministic decision trees
9.3 Lower bounds on the depth of decision trees
Exercises

11. Communication complexity

10.1 Communicaton matrix and protocol-tree
10.2 Non-deterministic communication complexity
10.3 Randomized protocols
Exercises

12. The complexity of algebraic computations

12.1 Multiplication and inversion of large matrices
12.2 Finite Fourier transform and computing with polynomials
12.3 Lower bounds on the number of operations
12.4 Algebraic complexity classes
Exercises

13. Circuit complexity

13.1 Circuit and formula complexity
13.2 Lower bounds on bounded-depth and monotone circuits
Exercises

14. Cryptography

14.1 A classical problem: one-time pads
14.2 Passwords and signatures
14.3 Public key cryptography
Exercises