[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/course/cs254b/kbhsu_cs254b_apr302025.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "SU-CS254B APR302025" source: https://www.jemoka.com/posts/kbhsu_cs254b_apr302025/ date: 2025-04-30 --- 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}\).