1
This graduate-level course focuses on current research topics in computational complexity theory.
FREE
This course includes
Hours of videos
499 years, 11 months
Units & Quizzes
18
Unlimited Lifetime access
Access on mobile app
Certificate of Completion
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 Currilcum
- 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
