H*: there’s a language A such that… A \in \text{TIME}\left(2^{O\left(n\right)}\right) \exists \delta >0 such that if C_{n} is a n-var circuit of size \leq 2^{\delta n} we have \text{Pr}\left[ C_{n}\left(x\right) = A_{n}\left(x\right)\right] \leq \frac{1}{2} + 2^{-\delta n} stretching randomness Goal: take S \sim \left\{\pm 1\right\}^{l}, we want to stretch this randomness \left\{\pm 1\right\}^{n} where n = 2^{\theta\left(l\right)}, l = \theta \left(\log n\right). Two main parts: combinatorial designs Yao’s Next-Bit Prediction Lemma We can choose sufficiently small l, in particular to be l = c \log n, because then we can iterate over all seeds in time 2^{l} = n^{c}.