Catalog Description: Topics will vary from semester to semester. See Computer Science Division announcements.
Units: 1-4
Formats:
Fall: 2.0-5.0 hours of lecture per week
Fall: 3.0-15.0 hours of lecture per week
Spring: 3.0-15.0 hours of lecture per week
Fall: 3.0-9.0 hours of lecture per week
Spring: 3.0-9.0 hours of lecture per week
Spring: 2.0-6.0 hours of lecture per week
Fall: 2.0-6.0 hours of lecture per week
Fall: 1.0-3.0 hours of lecture per week
Spring: 1.0-3.0 hours of lecture per week
Spring: 2.0-5.0 hours of lecture per week
Grading basis: letter
Final exam status: No final exam
Department Notes: Randomized algorithms give a broad and rich algorithmic toolkit (e.g., sampling, Monte Carlo methods). Randomness is an essential resource in distributed computing, cryptography, and interactive proofs. In this course, we would explore the role of randomness in computation: Can we derandomize algorithms without changing their time or space complexity? Can we "purify" randomness from a weak source of randomness? Pseudo-randomness is the property of "appearing random" while having little or no randomness. Pseudo-randomness plays a significant role in error-correcting codes, expander graphs, randomness extractors, and pseudo-random generators. In this course, we will see all these beautiful applications. In the second part of the course, we will focus on derandomization of small-space computation, also known as the "RL versus L" question. It asks whether all problems that can be decided in randomized logarithmic space (RL) can also be decided in deterministic logarithmic space (L). We will cover recent approaches towards showing that RL = L.
Related Areas: