Randomised Computation

Explore the fascinating world of randomised computation in this 31-minute talk by Daria Dicu. Delve into the concept of probabilistic Turing machines and their role in solving decision problems efficiently. Examine various complexity classes associated with randomised computation, including BPP, RP, and ZPP, and understand their relationships with familiar classes like P and NP. Discover how randomised algorithms outperform deterministic ones through the Schwartz-Zippel lemma applied to Polynomial Identity Testing. Investigate the open problem of P = BPP and learn about pseudorandom number generators for simulating randomised algorithms deterministically. Cover key topics such as Monte Carlo methods, non-deterministic Turing machines, randomised polynomial time, arithmetic circuit examples, and probabilistic algorithms.

Intro
Monte Carlo
Non-deterministic Turing Machine
RP (randomised polynomial time)
Arithmetic circuit example
Probabilistic algorithm
Simulation of a randomised algorithm