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.

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.

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-testing/decision);
- average-case complexity;

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.

- 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. - Optimization problem, self-reducibility,
the existence of NP-complete problems, CSAT is in NPC.

See On Teaching the Basics of Complexity Theory. - 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. - On P/poly and PH. (See notes.)
- cont. of last lecture + hierarchy and gap theorems.

See More resources, more power? - Space Complexity (part 1: the mind-set and log-space): See notes.
- Space Complexity (part 2: NL and PSPACE): See same notes.
- Ending space complexity and starting randomized computations.

See notes on Randomized Complexity Classes - Randomized Complexity Classes (cont.): See same notes.
- Exact Counting and Approximate Counting (via reduction to NP): See notes.
- Two topics: (1) On the Complexity of Unique Solutions, and (2) Uniform Generation and its relation to Approximate Counting. See notes.
- 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). - Worst-case hardness and average-case hardness: See Section 7.2 (and 7.1.3) in the 3rd part of the said draft.
- Pseudorandomness: general-purpose generators. See (mainly) Section 8.3 in the 4th part of the said draft.
- Pseudorandomness: derandomization. See (mainly) Section 8.4 in the 4th part of the said draft.
- Probabilistic proof systems: IP. See Section 9.1 in the 4th part of the said draft.
- 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. - PCP and approximation problems. See Sections 9.3.4 and 10.1.1 in the said draft.
- Average-case complexity. See Section 10.2 in the 5th part of the said draft.

Back to homepage.