Computational Complexity Theory

Computational Complexity Theory

0.0
(0) 0 Students
Download Brochure

What you will learn

  • none

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.

play
Lecture 1: Introduction
Preview 34:13
play
Lecture 2: NP Completeness
Preview 48:03
play
Lecture 3: SAT is NP-complete
Preview 43:52
play
Lecture 4: More on NP completeness
Preview 43:52

play
Lecture 05: Hierarchy Theorems
Preview 47:31
play
Lecture 06: Introduction to Space Complexity
Preview 47:33
play
Lecture 07: Savitch's Theorem
Preview 49:26

play
Lecture 08: Immerman-Szelepscenyi Theorem
Preview 48:20
play
Lecture 09: Polynomial Hierarchy
Preview 48:01
play
Lecture 10: A PSPACE Complete Problem
Preview 48:19

play
Lecture 11: More on Polynomial Hierarchy
Preview 46:33
play
Lecture 12: Alternating Turing Machines
Preview 40:27
play
Lecture 13: Equivalence of Quantifier and Oracle Based Definitions of Polynomial Hierarchy
Preview 43:11

play
Lecture 14: Boolean Circuits
Preview 62:55
play
Lecture 15: Shannon's Theorem and Karp-Lipton-Sipser Theorem
Preview 46:49
play
Lecture 16: Bounded Depth Circuit Classes
Preview 45:38

play
Lecture 17: Kannan's Theorem
Preview 12:53
play
Lecture 18: Probabilistic Complexity
Preview 42:27
play
Lecture 19: StrongBPP and WeakBPP
Preview 13:01
play
Lecture 20: One-sided and Zero-sided Error Probabilistic Complexity Classes
Preview 17:57

play
Lecture 21: Error Reduction for BPP
Preview 47:30
play
Lecture 22: BPP in PH and Logspace Randomized Classes
Preview 50:25
play
Lecture 23: Valiant-Vazirani Theorem - I
Preview 46:01

play
Lecture 24: Valiant-Vazirani Theorem - I
Preview 50:55
play
Lecture 25: Amplified version of Valiant-Vazirani Theorem
Preview 44:44
play
Lecture 26: Toda's Theorem - I
Preview 47:07
play
Lecture 27: Toda's Theorem - II
Preview 39:10

play
Lecture 28: Permanent and Determinant Functions
Preview 15:42
play
Lecture 29: Permanent is hard for #P
Preview 53:43
play
Lecture 30: Interactive Proofs
Preview 81:20

play
Lecture 31: Graph Non-Isomorphism is in IP[2]
Preview 45:50
play
Lecture 32: Set Lower Bound Protocol
Preview 42:31
play
Lecture 33: MA is in AM
Preview 39:04

play
Lecture 34: Sumcheck Protocol - I
Preview 29:15
play
Lecture 35: Sumcheck Protocol - II
Preview 48:29
play
Lecture 36: Parity not in AC0 - I
Preview 44:56
play
Lecture 37: Parity not in AC0 - II
Preview 50:55

play
Lecture 38 : Circuits with Counters
Preview 35:31
play
Lecture 39 : Communication Complexity - I
Preview 51:48
play
Lecture 40 : PCP Theorem
Preview 89:20
play
Lecture 41 : Communication Complexity - II
Preview 45:53
img
No Discussion Found

0.0

0 Reviews

5
0
4
0
3
0
2
0
1
0
Meet Your Instructor
@VTU COE
img

Instructor
3.3 Rating
8558 Students
802 Courses
About Instructor

VTU is one of the largest Technological Universities in India with 24 years of Tradition of excellence in Engineering & Technical Education, Research and Innovations. It came into existence in the year 1998 to cater the needs of Indian industries for trained technical manpower with practical experience and sound theoretical knowledge.

video

Free

  • Course Duration
    30 h 33 m 13 s
  • Course Level
    Intermediate
  • Student Enrolled
    0
  • Language
    English
This Course Includes
  • 30 h 33 m 13 s Video Lectures
  • 2 Quizzes
  • 0 Assignments
  • 0 Downloadable Resources
  • Full Lifetime Access
  • Certificate of Completion