CS 271. Randomness and Computation

Catalog Description: Computational applications of randomness and computational theories of randomness. Approximate counting and uniform generation of combinatorial objects, rapid convergence of random walks on expander graphs, explicit construction of expander graphs, randomized reductions, Kolmogorov complexity, pseudo-random number generation, semi-random sources.

Units: 3.0

Prerequisites: 170 and at least one course numbered 270-279.

Fall: 3 hours of lecture per week
Spring: 3 hours of lecture per week

Grading basis: letter

Final exam status: No final exam

Class Schedule (Spring 2018):
TuTh 9:30AM - 10:59AM, Soda 306 – Alistair Sinclair

Class homepage on inst.eecs

General Catalog listing

Related Areas: