Fractional Pseudorandom Generators
summary
Defines a fractional pseudorandom generator that outputs points in the solid cube and shows how a polarizing random walk converts such a fractional PRG into a true Boolean PRG under three conditions: the distribution is q-noticeable (each coordinate variance ≥ q), it is symmetric, and the function class is closed under restrictions. Provides constructions of fractional PRGs from random restriction lemmas or L1 Fourier tail bounds (level k mass ≤ b^k) and gives conversion costs roughly error ε → ε/q and seed blowup by about 1/q with about T = O((log n)/(ε q)) steps before rounding.
AI-written summary · about