CS4995:	Introduction to
	Computational Complexity(CVN)
	Fall 2005

Instructor: Rocco Servedio
Class Manager: Andrew Wan
Email: atw12@columbia.edu

---

CONTENTS

• Announcements,Reading and Homework
• Overview and Prerequisites
• Grading and Requirements
• Schedule of Lectures

---

LECTURES

• Lecture 1 Introduction to complexity theory. Models of computation and computational problems.
• Lecture 2 Basic resources for computation: time, space, nondeterminism. Associated complexity classes.
• Lecture 3 Basic resources and classes continued.
• Lecture 4 Basic resources and classes continued.
• Lecture 5 Relationships among resources: P vs NP, time versus space, etc.
• Lecture 6 Relationships among resources continued.
• Lecture 7 Relationships among resources continued.
• Lecture 8 Reductions and completeness: NP completeness, PSPACE completeness, etc.
• Lecture 9 Reductions and completeness continued.
• Lecture 10 Reductions and completeness continued.
• Lecture 11 Reductions and completeness continued.
• Lecture 12 Reductions and completeness continued.
• Lecture 13 Reductions and completeness continued.
• Lecture 14 Counting problems, #P.
• Lecture 15 Counting problems, #P continued.
• Lecture 16 Randomness as a computational resource; associated complexity classes.
• Lecture 17 Randomness continued.
• Lecture 18 Randomness continued.
• Lecture 19 Nonuniform models of computation; circuit complexity; lower bounds.
• Lecture 20 Nonuniform models, circuits, lower bounds continued.
• Lecture 21 Nonuniform models, circuits, lower bounds continued.
• Lecture 22 Nonuniform models, circuits, lower bounds continued.
• Lecture 23 Communication complexity.
• Lecture 24 Communication complexity continued.
• Lecture 25 Interactive proofs, IP=PSPACE.
• Lecture 26 Interactive proofs and probabilistically checkable proofs.