2026-07-22T16:55:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14746 2024-03-06T10:54:48Z ddc:004 open_access

Fourier Growth of Structured 𝔽₂-Polynomials and Applications Błasiok, Jarosław Ivanov, Peter Jin, Yaonan Lee, Chin Ho Servedio, Rocco A. Viola, Emanuele Fourier analysis Pseudorandomness Fourier growth We analyze the Fourier growth, i.e. the L₁ Fourier weight at level k (denoted L_{1,k}), of various well-studied classes of "structured" m F₂-polynomials. This study is motivated by applications in pseudorandomness, in particular recent results and conjectures due to [Chattopadhyay et al., 2019; Chattopadhyay et al., 2019; Eshan Chattopadhyay et al., 2020] 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 m F₂-polynomial p has L_{1,k}(p) ≤ Pr [p = 1] ⋅ O(d)^k. This quadratically strengthens an earlier bound that was implicit in [Omer Reingold et al., 2013]. - We show that any read-Δ degree-d m F₂-polynomial p has L_{1,k}(p) ≤ Pr [p = 1] ⋅ (k Δ d)^{O(k)}. - We establish a composition theorem which gives L_{1,k} bounds on disjoint compositions of functions that are closed under restrictions and admit L_{1,k} bounds. Finally, we apply the above structural results to obtain new unconditional pseudorandom generators and new correlation bounds for various classes of m F₂-polynomials. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jarosław Błasiok and Peter Ivanov and Yaonan Jin and Chin Ho Lee and Rocco A. Servedio and Emanuele Viola 2021 Is Part Of LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2021.53 urn:nbn:de:0030-drops-147462 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.53 eng https://creativecommons.org/licenses/by/4.0/legalcode