A two-semester course on Complexity Theory

Oded Goldreich


Introduction to Complexity Theory: Two-semester course
Last given in 2014-15 and 2016-17 in a supervised reading format (previously given in 2005-06, 2007-08, 2009-10, and 2012-2013).

A general suggested outline for the reading is provided by me (see HERE), but the actual implementation will be up to the students.

In a nutshell, Complexity Theory means the study of the limitation of efficient computation.

Format

The course will be based on my book on Computational Complexity, and will cover approximately half the material in that book. Students will be expected to read 10-20 pages a week, and to participate in a weekly meeting (of 1-2 hours). Each meeting will consist of two parts. In the 1st part, we will discuss the material read, and I will answer questions and/or add clarifications. In the 2nd part, I will motivate and/or provide an overview for the material to be read in coming week. (The students will get free access to an e-copy of the book.)

Participating students will be credited 2 points for each semester, where a pass grade will be given subject to submitting (light-weight) homework assignments that are marked as satisfactory.

Syllabus

Complexity Theory is concerned with the study of the intrinsic difficulty of computational tasks. This study tend to aim at generality: It focuses on natural computational resources, and the effect of limiting those on the class of problems that can be solved.

The (half-century) history of Complexity Theory has witnessed two main research efforts (or directions). The first direction is aimed towards actually establishing concrete lower bounds on the complexity of problems, via an analysis of the evolution of the process of computation. Thus, in a sense, the heart of this direction is a ``low-level'' analysis of computation. Most research in circuit complexity and in proof complexity falls within this category. In contrast, a second research effort is aimed at exploring the connections among computational problems and notions, without being able to provide absolute statements regarding the individual problems or notions. This effort may be viewed as a ``high-level'' study of computation, and the course will be confined to it. Specific topics will include:

This course has some overlap with the course Foundations of Cryptography. Specifically, one-way functions, pseodorandom generators, and zero-knowledge proofs are covered in both courses, but the perspective and the actual contents are different.

Prerequisites

There are no formal prerequisites for the course, but comfortable familiarity with the notion of an algorithm is definitely assumed. Students who did not take a course in "computability" (or "theory of computation") or are not sure about it, should study Section 1.2 in the book. This section discusses the notion of computational tasks and algorithms, while emphasizing the importance of representation.

The actual teaching as it took place in 2005-06

  1. The P-vs-NP Question (in search and decision forms), the notion of a reduction.
    See A brief overview to Complexity Theory (a teaser) and The preliminaries - computational tasks and model.
  2. Optimization problem, self-reducibility, the existence of NP-complete problems, CSAT is in NPC.
    See On Teaching the Basics of Complexity Theory.
  3. SAT is in NPC, NPI (i.e., $NP-(P+NPC)$), promise problems, optimal search algorithms, $NP \cap coNP$.
    See Four Advanced Topics Related to NP and NPC.
  4. On P/poly and PH. (See notes.)
  5. cont. of last lecture + hierarchy and gap theorems.
    See More resources, more power?
  6. Space Complexity (part 1: the mind-set and log-space): See notes.
  7. Space Complexity (part 2: NL and PSPACE): See same notes.
  8. Ending space complexity and starting randomized computations.
    See notes on Randomized Complexity Classes
  9. Randomized Complexity Classes (cont.): See same notes.
  10. Exact Counting and Approximate Counting (via reduction to NP): See notes.
  11. Two topics: (1) On the Complexity of Unique Solutions, and (2) Uniform Generation and its relation to Approximate Counting. See notes.
  12. Two unrelated topics: (1) Reducing Uniform Generation to NP, and (2) One-Way Functions.
    See, respectively, sections 6.2.4.2 and 7.1 in the 3rd part of my draft (of a book).
  13. Worst-case hardness and average-case hardness: See Section 7.2 (and 7.1.3) in the 3rd part of the said draft.
  14. Pseudorandomness: general-purpose generators. See (mainly) Section 8.3 in the 4th part of the said draft.
  15. Pseudorandomness: derandomization. See (mainly) Section 8.4 in the 4th part of the said draft.
  16. Probabilistic proof systems: IP. See Section 9.1 in the 4th part of the said draft.
  17. Probabilistic proof systems: PCP. See Section 9.3 in the 4th part of the said draft.
    Focus on Sections 9.3.1, 9.3.2.0 and 9.3.2.1.
  18. PCP and approximation problems. See Sections 9.3.4 and 10.1.1 in the said draft.
  19. Average-case complexity. See Section 10.2 in the 5th part of the said draft.


Back to homepage.