2026-07-25T16:14:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10829 2024-03-06T10:46:49Z ddc:004 open_access

Fourier Bounds and Pseudorandom Generators for Product Tests Lee, Chin Ho bounded independence plus noise Fourier spectrum product test pseudorandom generators We study the Fourier spectrum of functions f : {0,1}^{mk} -> {-1,0,1} which can be written as a product of k Boolean functions f_i on disjoint m-bit inputs. We prove that for every positive integer d, sum_{S subseteq [mk]: |S|=d} |hat{f_S}| = O(min{m, sqrt{m log(2k)}})^d . Our upper bounds are tight up to a constant factor in the O(*). Our proof uses Schur-convexity, and builds on a new "level-d inequality" that bounds above sum_{|S|=d} hat{f_S}^2 for any [0,1]-valued function f in terms of its expectation, which may be of independent interest. As a result, we construct pseudorandom generators for such functions with seed length O~(m + log(k/epsilon)), which is optimal up to polynomial factors in log m, log log k and log log(1/epsilon). Our generator in particular works for the well-studied class of combinatorial rectangles, where in addition we allow the bits to be read in any order. Even for this special case, previous generators have an extra O~(log(1/epsilon)) factor in their seed lengths. We also extend our results to functions f_i whose range is [-1,1]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chin Ho Lee 2019 Is Part Of LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2019.7 urn:nbn:de:0030-drops-108296 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.7 eng https://creativecommons.org/licenses/by/3.0/legalcode