Small-Bias Sets for Nonabelian Groups: Derandomizing the Alon-Roichman Theorem

Sixia Chen, Cristopher Moore, Alexander Russell

In analogy with epsilon-biased sets over Z_2^n, we construct explicit epsilon-biased sets over nonabelian finite groups G. That is, we find sets S subset G such that | Exp_{x in S}…