Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BOUNDED INDEPENDENCE PLUS NOISE:
Reports tagged with bounded independence plus noise:
TR19-017 | 6th February 2019
Chin Ho Lee

#### Fourier bounds and pseudorandom generators for product tests

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 ... more >>>

ISSN 1433-8092 | Imprint