#

### 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*
#### 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.

Volume 2020, Article 3

Volume 2020
Published articles