CS 8803-COR Complexity of Randomness
Spring 2015
Instructor: Lance Fortnow
Time and Location: MWF 11:05-11:55 Howey (Physics) N210
Description: We look at two aspects of the computational nature of randomness. In the first half of the class we consider Kolmogorov Complexity which measures the amount of randomness of some data by the size of its shortest description which yields a surprisingly deep and beautiful theory, as well as applications across computational complexity. In the second half we look at pseudorandom generators that can fool computations and tests of randomness. At the end we tie both of these notions together.
Prerequisites: A basic knowledge of Turing machines and the P v NP problem at the level of CS 4510.
Recommended Textbook: An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitányi
Coursework: Students will be asked to write scribe notes for several lectures and present a recent research paper related to randomness.
