A two-semester course on Complexity Theory

Oded Goldreich

The course will take place on Thursday, 14-16, in Room 1. The course will consist of 20 lectures, with 10 lectures given in each semester. The lectures will be given jointly by Or Meir and myself.

Participating students will be credited 1.5 points for each semester, where a pass grade will be given subject to submitting (light-weight) homework assignments that are marked as satisfactory. Or has created a mailing list for the course that can be joined by joining the following Google Group.

Syllabus

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:

• revisiting the P-vs-NP Question and NP-Completeness;
• separation results for time and space complexity;
• non-uniform complexity (e.g., P/poly);
• the Polynomial-time Hierarchy;
• space complexity (focus on log-space and NL);
• the class #P and approximate-#P;
• randomized computations (RP and BPP);
• probabilistic proof systesms (IP, ZK, and PCP);
• pseudorandomness (generators and derandomization);
• approximation (optimization/search and property/decision);
• average-case complexity;

A preliminary draft of a book that I'm using in this course is available from www.wisdom.weizmann.ac.il/~oded/cc-drafts.html; other related material is available from www.wisdom.weizmann.ac.il/~oded/cc-texts.html.

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.