Opening Randomized Complexity: RP, coRP, and ZPP
Randomized Complexity: RP, coRP, and ZPP
- Length
- 1 h 22 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 12: Introduction to randomized complexity
O'Donnell builds coin-flipping Turing machines, amplifies one-sided error, and puts COMPOSITES in RP via witnesses.
Randomized complexity treats random coin flips as a computational resource alongside time and space, in session 21 of O'Donnell's CMU 15-455 undergraduate complexity course. O'Donnell motivates the subject with problems where randomness gives fast algorithms: Miller-Rabin primality testing, median finding, Freivalds' matrix multiplication check and undirected connectivity. He formalizes probabilistic Turing machines with two transition functions and , measures worst-case time over coin flips, and defines RP by one-sided error. Success amplification by repetition drives the error down exponentially, and the inclusions of P in RP and of RP in NP follow. Random compositeness witnesses put COMPOSITES in RP, and O'Donnell defines ZPP as the intersection of RP and coRP. The material assumes P, NP and modular arithmetic; Sipser Ch. 10.2 is suggested reading.
Randomized complexity treats random coin flips as a computational resource alongside time and space, in session 21 of O'Donnell's CMU 15-455 undergraduate complexity course. O'Donnell motivates the subject with problems where randomness gives fast algorithms: Miller-Rabin primality testing, median finding, Freivalds' matrix multiplication check and undirected connectivity. He formalizes probabilistic Turing machines with two transition functions and , measures worst-case time over coin flips, and defines RP by one-sided error. Success amplification by repetition drives the error down exponentially, and the inclusions of P in RP and of RP in NP follow. Random compositeness witnesses put COMPOSITES in RP, and O'Donnell defines ZPP as the intersection of RP and coRP. The material assumes P, NP and modular arithmetic; Sipser Ch. 10.2 is suggested reading.

This lecture
Lecture 21 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. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in