Average Bias and Polynomial Sources

• Published in: arXiv.org 2019-05
• Main Authors: Bhattacharyya, Arnab, Philips, George John, Ghoshal, Suprovat, Meka, Raghu
• Format: Article
• Language: English
• Subjects: Bias; Entropy; Polynomials; Thermometers
• ISSN: 2331-8422

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 so low average bias is a stronger condition than high min-entropy. We observe that the inner product function is an extractor for any source with average bias less than \(2^{-n/2}\). The notion of average bias especially makes sense for polynomial sources, i.e., distributions sampled by low-degree \(n\)-variate polynomials over \(\mathbb{F}_2\). For the well-studied case of affine sources, it is easy to see that min-entropy \(k\) is exactly equivalent to average bias of \(2^{-k}\). We show that for quadratic sources, min-entropy \(k\) implies that the average bias is at most \(2^{-\Omega(\sqrt{k})}\). We use this relation to design dispersers for separable quadratic sources with a min-entropy guarantee.