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

Abstract

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.

• The article: PDF (263 KB)
• Source material: ZIP (81 KB)
• BibTeX entry for this article (252 bytes)

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

© 2020 Rohit Agrawal
Licensed under a Creative Commons Attribution License

Volume 2020, Article 3

Volume 2020

Published articles