Fourier bounds and pseudorandom generators for product tests
share
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, ∑_S ⊆ [mk]: |S|=d |f̂_̂Ŝ| = O(m)^d . Our upper bound is tight up to a constant factor in the O(·). Our proof builds on a new `level-d inequality' that bounds above ∑_|S|=df̂_̂Ŝ^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 Õ(m + (k/ε)), which is optimal up to polynomial factors in m, k and (1/ε). 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 Õ((1/ε)) factor in their seed lengths. Using Schur-convexity, we also extend our results to functions f_i whose range is [-1,1].
READ FULL TEXT