PART I - COMPLEXITY

Text: Complexity and Information, J.F. Traub and A.G. Werschulz, Cambridge University Press, 1998.

The softcover version costs about $28 and is available at the Columbia University Bookstore.

I will only cover the part of the text which requires no more than calculus. The following is an indication of what I´ll cover from the text.

1. Introduction, pp. 3 - 9
2. Integration Example, pp. 10 - 14
3. Breaking the Curse, pp. 24 - 40 (in part)
4. Mathematical Finance, pp. 43 - 52 (in part)
5. Model of Computation, pp. 65 - 69
6. Formal Models and Scientific Knowledge, pp. 70 - 73
7. Complexity of Linear Programming, pp. 74 - 76
8. Complexity of Verification, pp. 77 - 79
9. Clock Synchronization in Distributed Networks, pp. 91 - 93
10. Assigning Values to Mathematical Hypotheses, pp. 99 - 102

OPTIONAL MATERIAL

1. General Formulation, pp.14 - 20
2. Integration Example Concluded, pp. 21 - 23
3. Value of Information in Computation, pp. 94 - 98

A number of additional complexity topics will be covered in the lectures. There will be handouts for this material. Topics include

• Quantum computing (A very small taste)
• Playing 20 questions against a liar
• Continuous binary search
• Fast matrix multiplication
• Fast Fourier transform (FFT)
• Polynomial Evaluation
• Effect of precomputation

PART II - ALGORITHMS

The material on algorithms will be covered by handouts.