文章基本信息

标题：Coin Theorems and the Fourier Expansion
本地全文：下载
作者：Rohit Agrawal
期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2020
卷号：2020
页码：1-15
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：In this note we compare two measures of the complexity of a class F of Boolean functions studied in (unconditional) pseudorandomness: 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 F (the Fourier growth). We show that for coins with low bias ε = o(1/n), a function’s distinguishing advantage in the coin problem is essentially equivalent to ε 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 ε, and we discuss here the possibility of a converse.
关键词：coin problem;analysis of Boolean functions