Today : Tue, Apr 16, 2024

  • No meeting

Announcements

  • Feb 12 : Rescheduling lectures on Mar 25th and 26th to Mar 23, 10am - 12pm.
  • Feb 11 : Rescheduling lecture on Feb 11 (Monday, 8am) to Feb 15 (Friday, 2pm).
  • Feb 11 : The instructor contact hours for the course are fixed to be Fri, 2pm - 3: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:

There is a strict and formal pre-requisite for this course : Computability and Complexity (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 7 Marks = 42%)
  • Reading Project Work (28%)
    • Interim Meeting Evaluation (5%)
    • Work & Presentation (15%)
    • Report (8%)
  • Exam - Midsem (10%)
  • Exam+Viva - Endsem (20%)
    • 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.