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
Prerequisites: COMPSCI 170 and at least one course from the following: COMPSCI 270 - COMPSCI 279.
Formats:
Fall: 3.0 hours of lecture per week
Spring: 3.0 hours of lecture per week
Grading basis: letter
Final exam status: No final exam
Class Schedule (Fall 2022):
TuTh 09:30-10:59, Soda 310 –
Alistair SINCLAIR
Related Areas: