期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We analyze the Fourier growth, i.e. the L1 Fourier weight at level k (denoted L1k), of various well-studied classes of "structured" F2-polynomials. This study is motivated by applications in pseudorandomness, in particular recent results and conjectures due to [CHHL19,CHLT19,CGLSS20] which show that upper bounds on Fourier growth (even at level k=2) give unconditional pseudorandom generators. Our main structural results on Fourier growth are as follows: - We show that any symmetric degree-d F2-polynomial p has L1k(p)Pr[p=1]O(d)k, and this is tight for any constant k. This quadratically strengthens an earlier bound that was implicit in [RSV13]. - We show that any read- degree-d F2-polynomial p has L1k(p)Pr[p=1](kd)O(k). - We establish a composition theorem which gives L1k bounds on disjoint compositions of functions that are closed under restrictions and admit L1k bounds. Finally, we apply the above structural results to obtain new unconditional pseudorandom generators and new correlation bounds for various classes of F2-polynomials.
