Pseudorandom Generators from Polarizing Random Walks
summary
Presents a concrete reduction: any fractional PRG whose per-coordinate second moment is bounded away from zero (parameter p) and whose test class is closed under restrictions yields a standard PRG by taking T = O((1/p) log(n/ε)) independent copies, so seed length multiplies by T and error scales to εT. The conversion uses a polarizing random walk that rounds fractional points to cube vertices in O((1/avg X^2) log(n/ε)) steps. Constructs fractional PRGs by scaling an ε-biased source when the class has Fourier growth C^k, giving T ≈ O(C^2 log(n/ε)) and concrete bounds for sensitivity s and width-W branching programs.
AI-written summary · about