Pseudorandomness, symmetry, smoothing

This is one of those works that seem (to me, at least) the outcome of a staggering amount of time and thought… anyway, it provides new information on small-bias and bounded-uniformity distributions, answering several questions. We ended up making two papers. The first is here . The second is only a draft, but it is available on my webpage here. The second also contains several alternative proofs of a main result from the first (showing that small-bias does not fool smoothed thresholds). Some of these alternative proofs might be more intuitive, and one of them is actually the first we discovered. But in the end we put shorter arguments in the first that fit better with the theme of Krawtchouk polynomials.