Computational Complexity
Offered By: IIT Hyderabad via Swayam
Course Description
Overview
This course is an introduction to the area of computational complexity theory. We will see different models of computations and computational complexity classes. The computational models measure various different aspects of computation, like time, space, randomness, number of gates, amount of communication etc. The complexity classes classify different computational problems depending on their easiness or hardness as per these different models. We will also see how these complexity classes are related to each other. Many of the results are extremely interesting and use several interesting ideas.INTENDED AUDIENCE : Students of Computer Science discipline. This could be BTech students who are interested in Theory or MTech/PhD students.PREREQUISITES : Theory of Computation.
Syllabus
Week-1: Introduction to the course, Review of NP Completeness, P vs NP, Cook-Levin Theorem
Week-2: Time Hierarchy Theorem, Polynomial Hierarchy, Introduction to Space Complexity
Week-3: Savitch’s Theorem, NL-Completeness, NL = coNL Week-4: PSPACE Completeness, Space Hierarchy Theorem, Baker-Gill-Solovay Theorem
Week-5: Randomized Complexity Classes, BPP is in polynomial hierarchy
Week-6:Nonuniform computation, Circuit Complexity
Week-7: Parity not in AC^0
Week-8: Karp-Lipton Theorem, Adleman’s Theorem, Polynomial Identity Testing, Isolation Lemma, Perfect Matching is in NC^2
Week-9: #P and #P Completeness. Permanent is #P Complete.
Week-10: Valiant Vazirani Theorem and Toda’s Theorem
Week-11: Communication Complexity, Monotone depth lower bound for matching
Week-12: Interactive Proofs.
Week-2: Time Hierarchy Theorem, Polynomial Hierarchy, Introduction to Space Complexity
Week-3: Savitch’s Theorem, NL-Completeness, NL = coNL Week-4: PSPACE Completeness, Space Hierarchy Theorem, Baker-Gill-Solovay Theorem
Week-5: Randomized Complexity Classes, BPP is in polynomial hierarchy
Week-6:Nonuniform computation, Circuit Complexity
Week-7: Parity not in AC^0
Week-8: Karp-Lipton Theorem, Adleman’s Theorem, Polynomial Identity Testing, Isolation Lemma, Perfect Matching is in NC^2
Week-9: #P and #P Completeness. Permanent is #P Complete.
Week-10: Valiant Vazirani Theorem and Toda’s Theorem
Week-11: Communication Complexity, Monotone depth lower bound for matching
Week-12: Interactive Proofs.
Taught by
Prof. Subrahmanyam Kalyanasundaram
Tags
Related Courses
理论计算机科学基础 | Introduction to Theoretical Computer SciencePeking University via edX 算法设计与分析(高级) | Advanced Design and Analysis of Algorithms
Peking University via edX The Introduction to Quantum Computing
Saint Petersburg State University via Coursera Computational Complexity Theory
Indian Institute of Technology Kanpur via Swayam Theory of Computation, Fall 2020
Massachusetts Institute of Technology via YouTube