Course: Complexity Theory I (Part II)

Complexity Theory I (Part II)

Space bounded computation: PSPACE, NSPACE, L, NL, reductions, completeness, complementation.
Polynomial Hierarchy: Quantifier alternation, completeness, Alternating Turing Machines, Oracle Machines.
Circuits: Conditional lower bounds (Karp-Lipton Theorem, etc.), Circuit classes.
Randomized Computation: BPP, RP, coRP, ZPP, Error reduction, Adelman's Theorem, Randomized reductions, Randomized space computation.
Interactive Proofs: Definitions, Deterministic verifier, Probablisitic verifier, Public coins vs. Private coins.

(Same policy as Part I.)

4 Light Quizzes (Weightage: 30%, Best 3 of 4). 20 min MCQ Test to check your understanding of definitions and to ensure that you have gone through reading material.
- 16 Oct, 23 Oct, 6 Nov and 13 Nov.

3 Assignments (Weightage: 30%; Best 5 of 6; 3 Assignments in Part I). Problems will require longer to solve. You will need to upload written solutions. One of the assignments which will be harder can be assigned to a group of students. Groups will be formed by the instructors.
Dates for Release | Submission | Marks Release given bellow:
1. 12 Oct | 22 Oct | 29 Oct.
2. 22 Oct | 2 Nov | 9 Nov.
3. 2 Nov | 20 Nov | 27 Nov. (Group Assignment)

2 Deep Quizzes (Weightage: 30%; Best 3 of 4; 2 Quizzes in Part I). We will be doing timed exams of 1hr in moodle.
1. Between 28-30 Oct | Marks release by 10 Nov.
2. Between 25-27 Nov | Marks release by 7 Dec.

Scribe Notes or Presentations (Weightage: 10%). Students will be given a choice to scribe notes for a lecture or do presentations on an advanced topic. They will be evaluated on clarity of explaining the concepts. Some of the topics for presentation are listed in Part I. More will be added later.

Error reduction (recap), BPP vs. Circuits, BPP vs. PH: Notes. (Guest lecture by Suryajith Chillara.)