Bulletin Year: 2022 - 2023 Graduate Bulletin | View this course in the current bulletin.
CS 526 Randomness and Computation 4 cr.  (4-0-0)

This course provides an introduction to the fundamental ideas, concepts, and tools related to using randomness in computation. The ability of computers to generate random sequences and the fact that random bits can be used to design more efficient algorithms are among the most notable and surprising advancements in computer science.  Topics covered in this course include equality testing, Markov and Chebyshev inequalities, median finding, perfect hashing families, Chernoff bound and its applications, polynomial identity testing, the probabilistic method, the method of conditional probabilities, Randomized Data Structures, Markov Chains, randomized complexity classes, and derandomization.