• No products in the cart.

This graduate-level course focuses on current research topics in computational complexity theory. In this course topics include Nondeterministic, alternating, probabilistic, and parallel computation models and Boolean circuits.  In addition to that, Complexity classes and complete sets, The polynomial-time hierarchy, Interactive proof systems, Relativization, Definitions of randomness, Pseudo-randomness and derandomizations, Interactive proof systems and probabilistically checkable proofs will also be discussed in this course.


This course does not involve any written exams. Students need to answer 5 assignment questions to complete the course, the answers will be in the form of written work in pdf or word. Students can write the answers in their own time. Each answer needs to be 200 words (1 Page). Once the answers are submitted, the tutor will check and assess the work.


Edukite courses are free to study. To successfully complete a course you must submit all the assignment of the course as part of assessment. Upon successful completion of a course, you can choose to make your achievement formal by obtaining your Certificate at a cost of £49.

Having an Official Edukite Certification is a great way to celebrate and share your success. You can:

  • Add the certificate to your CV or resume and brighten up your career
  • Show it to prove your success



Course Credit: MIT

Course Curriculum

Module: 01
PH Time-Space Tradeoffs 00:05:00
Relativization 00:05:00
Circuits and Karp-Lipton 00:05:00
Unique-SAT, Parity-SAT, and Approximate Counting 00:05:00
Toda’s Theorem 00:05:00
AC0 Lower Bounds and Switching Lemma 00:05:00
Module: 02
Razborov-Smolensky 00:10:00
NEXP vs ACC0 (Addendum to Arora-Barak) 00:10:00
Communication Complexity 00:05:00
Lower Bounds for Deterministic Communication 00:05:00
Randomized Communication 00:05:00
Intro to PCP 00:10:00
Linearity Testing 00:05:00
Module: 03
Exponential Sized PCP 00:05:00
PCP with Polylogarithmic Queries and Sum Check 00:10:00
Unique Games Conjecture and Hardness for MAX-2LIN 00:05:00
P vs BPP 1 00:10:00
P vs BPP 2 00:10:00
Derandomization Implies Circuit Lower Bounds 00:10:00
Submit Your Assignment 00:00:00
Certification 00:00:00

Course Reviews


7 ratings
  • 5 stars0
  • 4 stars0
  • 3 stars0
  • 2 stars0
  • 1 stars0

No Reviews found for this course.

©2021 Edukite. All Rights Resereved
Edukite is A Part Of Ebrahim College, Charity Commission
Reg No 110841