Today : Sat, Dec 21, 2024

  • No meeting

Announcements

  • Mar 15 : Compensatory class on Mar 21, 10am - 11:30am (for Feb 17)
  • Mar 15 : Compensatory Class on Mar 28, 10am -11:30am
  • Feb 5 : Compensatory class on Feb 7, 11am.
  • 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.
  • Theme 2 : Probabilistic Proof Systems - Interactive Proofs, Arithemetization, IP=PSPACE, PCPs, inapproximability, Linearity testing, PCP theorem, Dinur's Combinatorial Proof.
  • Theme 3 : 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 4 : 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.

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 (35%)
  • Course Project Work (40%)
    • Interim Meeting Evaluation (10%)
    • Project Presentation (15%)
    • Overall involvement in the Work (5%)
    • Project Report (10%)
  • Exam+Viva(25%)
    • For an 'S' grade one needs to score more than 90 in the over all evaluation. 'A' will be 80, 'B' will be 70, 'C' will be 60, 'D' will be 50, 'E' will be 40 and below 40 is the fail grade.