ECCC-Report TR19-017https://eccc.weizmann.ac.il/report/2019/017Comments and Revisions published for TR19-017en-usThu, 07 Feb 2019 16:59:22 +0200
Paper TR19-017
| Fourier bounds and pseudorandom generators for product tests |
Chin Ho Lee
https://eccc.weizmann.ac.il/report/2019/017 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]$.
Thu, 07 Feb 2019 16:59:22 +0200https://eccc.weizmann.ac.il/report/2019/017