This graduate-level course focuses on current research topics in computational complexity theory.
September 23, 2022
English
English [CC]
Description
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
1916
Students
Massachusetts Institute of Technology
FREE
Hours of videos
Units & Quizzes
Unlimited Lifetime access
Access on mobile app
Certificate of Completion
- For teams of 2 or more users
- 27,000+ fresh & in-demand courses
- Learning Engagement tools
- SSO and LMS Integrations