Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-017 | 6th February 2019 05:43

Fourier bounds and pseudorandom generators for product tests


Authors: Chin Ho Lee
Publication: 7th February 2019 16:59
Downloads: 945


We study the Fourier spectrum of functions $f\colon \{0,1\}^{mk} \to \{-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(m)^d .
Our upper bound is tight up to a constant factor in the $O(\cdot)$. Our proof 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 $\tilde O(m + \log(k/\varepsilon))$, which is optimal up to polynomial factors in $\log m$, $\log\log k$ and $\log\log(1/\varepsilon)$. 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 $\tilde O(\log(1/\varepsilon))$ factor in their seed lengths.

Using Schur-convexity, we also extend our results to functions $f_i$ whose range is $[-1,1]$.

ISSN 1433-8092 | Imprint