All reports by Author Philips George John:

__
TR19-079
| 28th May 2019
__

Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka#### Average Bias and Polynomial Sources

Revisions: 2

Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka

We identify a new notion of pseudorandomness for randomness sources, which we call the average bias. Given a distribution $Z$ over $\{0,1\}^n$, its average bias is: $b_{\text{av}}(Z) =2^{-n} \sum_{c \in \{0,1\}^n} |\mathbb{E}_{z \sim Z}(-1)^{\langle c, z\rangle}|$. A source with average bias at most $2^{-k}$ has min-entropy at least $k$, and ... more >>>