首页    期刊浏览 2024年12月01日 星期日
登录注册

文章基本信息

  • 标题:Coin Theorems and the Fourier Expansion
  • 本地全文:下载
  • 作者:Rohit Agrawal
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-12
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In this note we compare two measures of the complexity of a class of Boolean functions studied in (unconditional) pseudorandomness: '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 (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 ; Fourier analysis
国家哲学社会科学文献中心版权所有