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.
Assessment
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.
Certification
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 | ||
| Assessment | |||
| Submit Your Assignment | 00:00:00 | ||
| Certification | 00:00:00 | ||
Course Reviews
No Reviews found for this course.
