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. 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.
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 ( 40%)
- Course Project Work ( 35%)
- Exams (Mid Sem + End Sem) ( 25%)