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, Arithmetization, IP=PSPACE, PCPs, inapproximability, Linearity testing, PCP theorem.
Course Pre-requisites:
There is a strict and formal prerequisite for this course: Computability and Complexity (CS6014).
Evaluation:
Grades will depend on four parameters listed in activities page with the following weightage.
- Problem Sets (5 x 8 Marks = 40%)
- Reading/Research Project Work (40%)
- Interim Meeting Evaluation (10%)
- Work & Presentation (20%)
- Report (10%)
- Exam+Viva - Midsem (10%)
- Exam+Viva - Endsem (10%) We will follow the "relative absolute grading" scheme. That is, the cutoffs for S, A, B, C, D, and E are going to be 85-90, 75-80, 65-70, 55-60, 45-50, and 35-40, respectively. The exact cut off will be determined based on the class average and related statistical parameters.