home | draft and extras | teaching plans | errata

5) Supplementary or main text for graduate or advanced undergraduate mathematics courses on computability.

1) Supplementary text for an Introduction to Theory of Computation course - 3rd/4th year undergrad course in CS, often mandatory.

2) Main text for an Introduction to Computational Complexity course - 4th year undergrad / 1st year graduate course.

3) Main text for a Graduate Computational Complexity course - 1st year graduate course for theory students.

4) Supplementary or main text for various seminars on computational complexity for advanced graduate students on topics such as "PCP and Hardness of Approximations", "Derandomization", or "Lower bounds for conrete computational models".

''Supplementary text for an Introduction to Theory of Computation course - 3rd/4th year undergrad course in CS, often mandatory. ''

''Main text for an Introduction to Computational Complexity course - 4th year undergrad / 1st year graduate course. ''

Main text for a Graduate Computational Complexity course - 1st year graduate course for theory students.

This is a course for graduate students interested in doing research in computational complexity and other related fields in theoretical computer science. Such a course would quickly review the background from Part I, and move on to the more advanced topics of Part II and III.

''Supplementary text for various seminars on computational complexity for advanced graduate students on topics such as "PCP and Hardness of Approximations", "Derandomization", or "Lower bounds for conrete computational models". ''

Computational Complexity: A Modern Approach

Textbook by Sanjeev Arora and Boaz Barak, Cambridge University Press.

complexitybook@gmail.com

home | draft and extras | teaching plans

Note: If you are using this book in your course, please let us know about this at complexitybook@gmail.com. Also, if you want to teach a course based on this book before March 2009, we can send you a version of the book that is more updated than the draft available online.

This book can be used for the following types of courses:

• Supplementary text for an Introduction to Theory of Computation course - 3rd/4th year undergrad course in CS, often mandatory.

This course is often taught using Sipser's excellent text of the same name. Part I of our text can be used to supplement Sipser's text with more modern coverage of topics that undergraduate may perhaps find more exciting than, say, automata theory, such as: interactive proofs, cryptography, quantum computing, PCP and hardness of approximation.

Example courses: Great Ideas in Theoretical Computer Science / Scott Aaronson at MIT

• Main text for an Introduction to Computational Complexity course - 4th year undergrad / 1st year graduate course.

This is a first course on computational complexity for undergraduate interested in this topic, and general graduate students (not necessarily those who want to do research in complexity).

Example courses: Computational Complexity / Amos Beimel and Kobbi Nissim at Ben-Gurion University, Computational Complexity / Amnon Ta-Shma and Oded Regev at Tel-Aviv University.

• Main text for a Graduate Computational Complexity course - 1st year graduate course for students interested in theoretical computer science.

Example courses: our own course at Princeton, Computational Complexity / Joan Feigenbaum at Yale , Computational Complexity / Kamesh Munagala at Duke , Manoj Prabhakaran at UIUC, see also Steven Rudich's course at CMU.

• Supplementary text for various seminars on computational complexity for advanced graduate students on topics such as "PCP and Hardness of Approximations", "Derandomization", or "Lower bounds for conrete computational

models".

fdfd