Chicago Journal of Theoretical Computer Science

Volume 2020

Article 4

Published by the Department of Computer Science, The University of Chicago.

Coin Theorems and the Fourier Expansion

Rohit Agrawal
Department of Computer Science
Harvard University
Cambridge, MA, USA
rohitagr AT seas DOT harvard DOT edu

August 31, 2020


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{F}$ (the Fourier growth). We show that for coins with low bias $\epsilon = o(1/n)$, a function's distinguishing advantage in the coin problem is essentially equivalent to $\epsilon$ times the sum of its level $1$ Fourier coefficients, which in particular shows that known level $1$ and total influence bounds for some classes of interest (such as constant-width read-once branching programs) in fact follow as a black-box from the corresponding coin theorems, thereby simplifying the proofs of some known results in the literature. For higher levels, it is well-known that Fourier growth bounds on all levels of the Fourier spectrum imply coin theorems, even for large $\epsilon$, and we discuss here the possibility of a converse.

Submitted Submitted June 10, 2019, revised August 11, 2020, published August 31, 2020.

DOI: 10.4086/cjtcs.2020.004

[] Volume 2020, Article 3
[back] Volume 2020 [back] Published articles
[CJCTS home]