Video Lectures
Lecture 23: Probabilistic Computation, BPP
Description: Quickly reviewed last lecture. Defined probabilistic Turing machines and the class BPP. Sketched the amplification lemma. Introduced branching programs and read-once branching programs. Started the proof that \(EQ\)ROBP ∈ BPP. Introduced the arithmetization method.
Instructor: Prof. Michael Sipser
Viewing videos requires an internet connection
Course Info
Instructor
As Taught In
Fall
2020
Level
Topics
Learning Resource Types
theaters
Lecture Videos
assignment
Problem Sets
grading
Exams
notes
Lecture Notes
Instructor Insights