Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-087 | 29th August 2020 19:35

Coin Theorems and the Fourier Expansion

RSS-Feed




Revision #1
Authors: Rohit Agrawal
Accepted on: 29th August 2020 19:35
Downloads: 427
Keywords: 


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 $\varepsilon = o(1/n)$, a function's distinguishing advantage in the coin problem is essentially equivalent to $\varepsilon$ 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 $\varepsilon$, and we discuss here the possibility of a converse.


Paper:

TR19-087 | 10th June 2019 00:14

Coin Theorems and the Fourier Expansion





TR19-087
Authors: Rohit Agrawal
Publication: 11th June 2019 17:34
Downloads: 796
Keywords: 


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 $\varepsilon = o(1/n)$, a function's distinguishing advantage in the coin problem is essentially equivalent to $\varepsilon$ 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 $\varepsilon$, and we discuss here the possibility of a converse.



ISSN 1433-8092 | Imprint