YoVDO

Computational Complexity Theory

Offered By: Indian Institute of Technology Kanpur via Swayam

Tags

Computer Science Courses Engineering Courses NP-completeness Courses Computational Complexity Theory Courses Space Complexity Courses Circuit Complexity Courses

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

Syllabus

COURSE LAYOUT

Week 1:NP CompletenessWeek 2:Hierarchy Theorems, Space ComplexityWeek 3:Space Complexity (contd)Week 4:Polynomial Hierarchy
Week 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

Introduction to Logic
Stanford University via Coursera
Control of Mobile Robots
Georgia Institute of Technology via Coursera
Nanotechnology: The Basics
Rice University via Coursera
Image and Video Processing: From Mars to Hollywood with a Stop at the Hospital
Duke University via Coursera
Exploring Engineering
Brown University via Canvas Network