Basic Information

Course Objectives:
The aim is to help the student to understand the modern and advanced concepts in computational complexity theory.

Syllabus:
Building upon the syllabus for CS6014, we will cover the following (divided into themes)

Theme 1 : Probabilistic Computation and Counting Complexity - Probabilistic Computation. Probabilistic Complexity Classes: RP, BPP and PP. Amplification of success probability . Functional Problems, Counting, related complexity classes, #P, Permanent, #P-completeness, Toda's theorem.
Theme 2 : Circuit Complexity and Lower Bounds - Review of P/poly, Boolean Circuits, Basic circuit design and complexity classes. Decision trees, Branching Programs, Uniformity, Basic containments and Simulations - Parity is not in AC^0 - three different proofs, Monotone circuit lower bounds, Power of negations in circuits. Algebraic Complexity.
Theme 3 : Hardness vs Randomness - Derandomization Problem. Derandomization of time and space bounded computations. A deterministic algorithm for undirected s-t connectivity. Explicit objects: PRGs, Extractors. Circuit lower bounds from PRGs, Nisan-Wigderson Generator, From worst case to average case. PRGs from hard functions. Derandomizing ACIT implies circuit lower bounds.
Theme 4 : Probabilistic Proof Systems - Interactive Proofs, Arithemetization, IP=PSPACE, PCPs, inapproximability, Linearity testing, PCP theorem, Dinur's Combinatorial Proof.

Course Pre-requisites:
For the masters and PhD students a formal pre-requisite is the Advanced Theory of Computation (CS6014). IITM system allows undergrad students to get "consent of teacher" and register for the course. The course will assume basics of complexity theory that is done in CS6014.
Evaluation:
Grades will depend on four parameters listed in activities page with the following weights.

• Problem Sets ( 45%)
• Course Project Work ( 30%)
  1. Interim evaluation: 10%
  2. Project presentation: 15%
  3. Project report 5%
• Exams ( 25%)
  1. Tutorials 10%
  2. End Sem 15%