Advanced Topics in Computational Randomness

Last Updated: Spring 2025

1. Credits and contact hours: 3 credits, 3 contact hours
2. Textbook, title, author, and year: None
3. Other supplemental materials: None

Specific course information

1. Brief description of the content of the course: Advanced study of the role of randomness in computation. Randomized algorithms, derandomization, and probabilistic complexity classes. Kolmogorov complexity, algorithmic information theory, and algorithmic randomness. Applications chosen from cryptography, interactive proof systems, computational learning, lower bound arguments, mathematical logic, and the organization of complex systems. Novel models of computation emerging in a rapidly changing field.
2. Prerequisites or co-requisites: COMS 5310 or an equivalent in which you wrote many proofs; graduate classification or permission of instructor