0
(
ratings
)
1
students
Created by:
Last updated:
September 23, 2022
Duration:
Unlimited Duration
FREE
This course includes:
Unlimited Duration
Badge on Completion
Certificate of completion
Unlimited Duration
Description
This graduate-level course focuses on current research topics in computational complexity theory.
Topics include: Nondeterministic, alternating, probabilistic, and parallel computation models; Boolean circuits; 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.
Course Curriculum
- PH Time-Space Tradeoffs Unlimited
- Relativization Unlimited
- Circuits and Karp-Lipton Unlimited
- Unique-SAT, Parity-SAT, and Approximate Counting Unlimited
- Toda’s Theorem Unlimited
- AC0 Lower Bounds and Switching Lemma Unlimited
- Razborov-Smolensky Unlimited
- NEXP vs ACC0 (Addendum to Arora-Barak) Unlimited
- Communication Complexity 1 Unlimited
- Lower Bounds for Deterministic Communication Unlimited
- Randomized Communication Unlimited
- Intro to PCP Unlimited
- Linearity Testing Unlimited
- PCP with Polylogarithmic Queries and Sum Check Unlimited
- Unique Games Conjecture and Hardness for MAX-2LIN Unlimited
- P vs BPP 1 Unlimited
- P vs BPP 2 Unlimited
- Derandomization Implies Circuit Lower Bounds Unlimited
About the instructor
5
5
Instructor Rating
1
Reviews
1520
Courses
1906
Students
Massachusetts Institute of Technology