H*: there’s a language \(A\) such that…
- \(A \in \text{TIME}\qty(2^{O\qty(n)})\)
- \(\exists \delta >0\) such that if \(C_{n}\) is a n-var circuit of size \(\leq 2^{\delta n}\) we have \(\text{Pr}\qty[ C_{n}\qty(x) = A_{n}\qty(x)] \leq \frac{1}{2} + 2^{-\delta n}\)
stretching randomness
Goal: take \(S \sim \qty {\pm 1}^{l}\), we want to stretch this randomness \(\qty {\pm 1}^{n}\) where \(n = 2^{\theta\qty(l)}, l = \theta \qty(\log n)\).
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}\).