Computational Complexity Theory
Offered By: Indian Institute of Technology Kanpur via Swayam
Course Description
Overview
In this course we study mathematical techniques that enable us to show the power and limitations of various computational models. We consider these models by putting restrictions on the resources that the model can use and study the class of problems that are solvable by these models. We also compare the various classes that are thus obtained and try to give relations between them.
INTENDED AUDIENCE :Advanced undergraduate and postgraduate studentsPREREQUISITES : Design and Analysis of Algorithms, Theory of ComputationINDUSTRIES SUPPORT :None
INTENDED AUDIENCE :Advanced undergraduate and postgraduate studentsPREREQUISITES : Design and Analysis of Algorithms, Theory of ComputationINDUSTRIES SUPPORT :None
Syllabus
COURSE LAYOUT
Week 1:NP CompletenessWeek 2:Hierarchy Theorems, Space ComplexityWeek 3:Space Complexity (contd)Week 4:Polynomial HierarchyWeek 5:Circuit ComplexityWeek 6:Randomized ComplexityWeek 7:Valiant Vazirani TheoremWeek 8:Toda’s Theorem, Complexity of Permanent function
Week 9:Interactive ProofsWeek 10:Interactive Proofs (contd)Week 11:Circuit Lower BoundsWeek 12:Communication Complexity, PCP Theorem
Taught by
Prof. Raghunath Tewari
Tags
Related Courses
Computational ComplexityIIT Hyderabad via Swayam Proof and Circuit Complexity - Robert Robere
Institute for Advanced Study via YouTube Quantum Complexity - Quantum Computation at CMU
Ryan O'Donnell via YouTube Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
Association for Computing Machinery (ACM) via YouTube Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
IEEE via YouTube