Opening Probabilistic Computation
Probabilistic Computation
- Length
- 1 h 23 min
- Level
- Undergraduate
- Recorded
- MIT2021
Chapter 1 of 10: Before the lecture
Proves equivalence of read-once branching programs is in BPP by evaluating them on finite-field inputs.
Testing whether two read-once branching programs compute the same Boolean function is a BPP problem, and Sipser proves it in session 23 of MIT 18.404J. He opens by reviewing probabilistic Turing machines and BPP, with a note on pseudorandom generators and the P versus BPP question. Arithmetization replaces AND and OR with multiplication and addition, so a worked exclusive-or program can be evaluated on non-Boolean field elements. The Schwartz–Zippel lemma bounds the roots of low-degree polynomials, and symbolic execution shows that the read-once condition keeps output polynomials multilinear. The argument assumes BPP, branching programs and elementary polynomial algebra.
Testing whether two read-once branching programs compute the same Boolean function is a BPP problem, and Sipser proves it in session 23 of MIT 18.404J. He opens by reviewing probabilistic Turing machines and BPP, with a note on pseudorandom generators and the P versus BPP question. Arithmetization replaces AND and OR with multiplication and addition, so a worked exclusive-or program can be evaluated on non-Boolean field elements. The Schwartz–Zippel lemma bounds the roots of low-degree polynomials, and symbolic execution shows that the read-once condition keeps output polynomials multilinear. The argument assumes BPP, branching programs and elementary polynomial algebra.

This lecture
Lecture 23 of 25 of Theory of Computation.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in