Lecture 23: Probabilistic Computation, BPP

Om kurset

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