Today : Thu, Jul 18, 2024

  • No meeting

Announcements

  • Mar 27 : Problem Set 4 posted. Due on Apr 3, 5pm.
  • Mar 21 : Course Project Topics announced.
  • Mar 16 : Extra Lecture on Mar 17, 4:30pm.
  • Older announcements.
Back to Courses

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 : Counting Complexity - Functional Problems, Counting, related complexity classes, #P, Permanent, #P-completeness, Toda's theorem. Randomized Algorithms in terms of counting. BPP, RP. BPP is in PH, BPP is in P/poly.
  • 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, PRGs, Extractors, Circuit lower bounds from PRGs, Nisan-Wigderson Generator, From worst case to average case. PRGs from hard functions.
  • Theme 4 : Probabilistic Proof Systems - Interactive Proofs, Arithemetization, IP=PSPACE, PCPs, inapproximability, Linearity testing, PCP theorem (without 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 the basic complexity theory that is done in CS6014.

Evaluation:

The course grading will be done in "absolute" scale rather than "relative" scale. Grades will depend on four parameters listed in activities page with the following weightage.

  • Problem Sets (6 x 6 = 36%)
  • Course Project Work (24%)
    • Interim Meeting Evaluation (6%)
    • Project Work & Presentation (12%)
    • Project Report(6%)
  • Exam+Viva - Midsem (15%)
  • Exam+Viva - Midsem (25%)
    • For an 'S' grade one needs to score more than 85 in the over all evaluation. 'A' will be 75, 'B' will be 65, 'C' will be 55, 'D' will be 45, 'E' will be 35 and below 35 is the fail grade.