Lee, Chin Ho
Fourier Bounds and Pseudorandom Generators for Product Tests
Abstract
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 mbit 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 Schurconvexity, and builds on a new "leveld 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 wellstudied 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].
BibTeX  Entry
@InProceedings{lee:LIPIcs:2019:10829,
author = {Chin Ho Lee},
title = {{Fourier Bounds and Pseudorandom Generators for Product Tests}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {7:17:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771160},
ISSN = {18688969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10829},
URN = {urn:nbn:de:0030drops108296},
doi = {10.4230/LIPIcs.CCC.2019.7},
annote = {Keywords: bounded independence plus noise, Fourier spectrum, product test, pseudorandom generators}
}
2019
Keywords: 

bounded independence plus noise, Fourier spectrum, product test, pseudorandom generators 
Seminar: 

34th Computational Complexity Conference (CCC 2019)

Issue date: 

2019 
Date of publication: 

2019 