摘要：We propose a new framework for constructing pseudorandom generators for
n-variate Boolean functions. It is based on two new notions. First, we introduce fractional
pseudorandom generators, which are pseudorandom distributions taking values in [−1,1]
n
.
Next, we use a fractional pseudorandom generator as steps of a random walk in [−1,1]
n
that
converges to {−1,1}
n
. We prove that this random walk converges fast (in time logarithmic in
n) due to polarization. As an application, we construct pseudorandom generators for Boolean
functions with bounded Fourier tails. We use this to obtain a pseudorandom generator for
functions with sensitivity s, whose seed length is polynomial in s. Other examples include
functions computed by branching programs of various sorts or by bounded-depth circuits.
