Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with product test:
TR17-090 | 15th May 2017
Chin Ho Lee, Emanuele Viola

The coin problem for product tests

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

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