Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BIAS VS LOW RANK:
Reports tagged with bias vs low rank:
TR19-079 | 28th May 2019
Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka

Average Bias and Polynomial Sources

Revisions: 2

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




ISSN 1433-8092 | Imprint