Random Walks on Expanders

k-wise Independence

Error Correcting Codes

SL=L

Code concatenation

Expander Mixing Lemma

Existence of Seeded-Extractors

Next-Bit Unpredictability

Discrete Fourier Analysis

Cheeger's Inequality

Error reduction

Graph Theoretic View

Trevisan's Extractor

Combinatorics

Pseudorandom generator (PRG)

Expander Graphs

Randomness Extractors

Small biased distributions

Leftover Hash Lemma

Nisan-Wigderson Construction

Max-Cut

ε-Biased Distributions

Zig-Zag Product

Spectral Expansion

Samplers

Two-Source Extractor

CS 294-202 Pseudorandomness UC Berkeley Fall 2021 This course explores the role of randomness in computation and pseudorandomness, focusing on the applications in error-correcting codes, expander graphs, randomness extractors, and pseudo-random generators. The course will also address the question of derandomization of small-space computation. Prerequisites are unspecified, but the course content suggests a high level of expertise. 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 would focus on the question of 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 would cover recent approaches towards showing that RL = L.    Salil Vadhan -  [Pseudorandomness](https://www.google.com/url?q=https%3A%2F%2Fpeople.seas.harvard.edu%2F~salil%2Fpseudorandomness%2F&sa=D&sntz=1&usg=AOvVaw2jc9ipUift6CNRnbiOuSkb)

CS 294-202 Pseudorandomness

Theoretical Computer Science

Expander walk sampling

Random Walks on Expanders

1 courses cover this concept

CS 294-202 Pseudorandomness