---
title: "SU-CS254B APR302025"
source: https://www.jemoka.com/posts/kbhsu_cs254b_apr302025/
date: 2025-04-30
---

H*: there&rsquo;s a language \(A\) such that&hellip;
\(A \in \text{TIME}\qty(2^{O\qty(n)})\) \(\exists \delta &gt;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&rsquo;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}\).
