Chin Ho Lee, Emanuele Viola

Let $X_{m, \eps}$ be the distribution over $m$ bits $(X_1, \ldots, X_m)$

where the $X_i$ are independent and each $X_i$ equals $1$ with

probability $(1+\eps)/2$ and $0$ with probability $(1-\eps)/2$. We

consider the smallest value $\eps^*$ of $\eps$ such that the distributions

$X_{m,\eps}$ and $X_{m,0}$ can be distinguished with constant

more >>>

Chin Ho Lee

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