Home » Course Layouts » Free Course Layout Udemy
This graduate-level course focuses on current research topics in computational complexity theory.
0
1
English
English [CC]
FREE
- Learn basic syntax that can apply to any language.
- Learn what is a programming language and the basic concepts for beginners.
- Understand what is Javascript in it's truest form.
- Know the basic syntax of Javascript.
- Know some hidden quirks in Javascript.
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 content
- 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
Instructor
Massachusetts Institute of Technology
5
5
1
1916
1520
