Opening BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
- Length
- 1 h 20 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 10: Before the lecture
Amplifies BPP's error with a Chernoff bound, then uses it to place BPP in P/poly and to sketch a route to P = BPP.
BPP is the class of languages decided in polynomial time by a probabilistic Turing machine that errs with probability at most on every input. Guruswami gives this guest lecture in CMU 15-455, placing BPP among P, RP, coRP and ZPP. A Chernoff bound shows that repeated runs with a majority vote drive the error down exponentially. Recasting the machine as deterministic with an auxiliary random tape puts BPP inside polynomial space, exponential time and polynomial-size circuits. The session closes with derandomization: hardness amplified through list-decodable codes, and pseudorandom generators that would give .
BPP is the class of languages decided in polynomial time by a probabilistic Turing machine that errs with probability at most on every input. Guruswami gives this guest lecture in CMU 15-455, placing BPP among P, RP, coRP and ZPP. A Chernoff bound shows that repeated runs with a majority vote drive the error down exponentially. Recasting the machine as deterministic with an auxiliary random tape puts BPP inside polynomial space, exponential time and polynomial-size circuits. The session closes with derandomization: hardness amplified through list-decodable codes, and pseudorandom generators that would give .
This lecture
Lecture 22 of 28 of Undergraduate Complexity Theory.
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.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in