Pseudorandomness, symmetry, smoothing: I
<|reference_start|>Pseudorandomness, symmetry, smoothing: I: We prove several new results about bounded uniform and small-bias distributions. A main message is that, small-bias, even perturbed with noise, does not fool several classes of tests better than bounded uniformity. We prove this for threshold tests, small-space algorithms, and small-depth circuits. In particular, we obtain small-bias distributions that   1) achieve an optimal lower bound on their statistical distance to any bounded-uniform distribution. This closes a line of research initiated by Alon, Goldreich, and Mansour in 2003, and improves on a result by O'Donnell and Zhao.   2) have heavier tail mass than the uniform distribution. This answers a question posed by several researchers including Bun and Steinke.   3) rule out a popular paradigm for constructing pseudorandom generators, originating in a 1989 work by Ajtai and Wigderson. This again answers a question raised by several researchers. For branching programs, our result matches a bound by Forbes and Kelley.   Our small-bias distributions above are symmetric. We show that the xor of any two symmetric small-bias distributions fools any bounded function. Hence our examples cannot be extended to the xor of two small-bias distributions, another popular paradigm whose power remains unknown. We also generalize and simplify the proof of a result of Bazzi.<|reference_end|>
@article{derksen2024pseudorandomness,,
    title={Pseudorandomness, symmetry, smoothing: I},
    author={Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola},
    journal={arXiv preprint arXiv:2405.13143},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.13143},
    primaryClass={cs.CC}
}