Explore randomized complexity theory in this undergraduate lecture focusing on RP, coRP, and ZPP classes. Delve into the concepts of probabilistic Turing machines, randomness, and nondeterminism. Learn about error amplification and randomized polynomial time algorithms. Gain insights into why randomness is important in computational complexity and understand the conditions for these complexity classes. Part of Carnegie Mellon's Computational Complexity Theory course (15-455), this lecture is taught by Ryan O'Donnell and complements Sipser's textbook chapter 10.2.
Undergrad Complexity at CMU - Randomized Complexity- RP, coRP, and ZPP
Overview
Syllabus
Introduction
Why RP
Why not randomness
Questions
probabilistic Turing Machine
Randomness
Conditions
Nondeterminism
Error amplification
Randomized polynomial time
Taught by
Ryan O'Donnell
