In this note we compare two measures of the complexity of a class \mathcal F of Boolean functions studied in (unconditional) pseudorandomness: \mathcal F's ability to distinguish between biased and uniform coins (the coin problem), and the norms of the different levels of the Fourier expansion of functions in $\mathcal ... more >>>

Blasiok (SODA'18) recently introduced the notion of a subgaussian sampler, defined as an averaging sampler for approximating the mean of functions f:\{0,1\}^m \to \mathbb{R} such that f(U_m) has subgaussian tails, and asked for explicit constructions. In this work, we give the first explicit constructions of subgaussian samplers (and in fact ... more >>>