TR17-136 Authors: Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

Publication: 10th September 2017 17:39

Downloads: 333

Keywords:

Let $\mathcal{F}$ be a finite alphabet and $\mathcal{D}$ be a finite set of distributions over $\mathcal{F}$. A Generalized Santha-Vazirani (GSV) source of type $(\mathcal{F}, \mathcal{D})$, introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence $(F_1, \dots, F_n)$ in $\mathcal{F}^n$, where $F_i$ is a sample from some distribution $d \in \mathcal{D}$ whose choice may depend on $F_1, \dots, F_{i-1}$.

We show that all GSV source types $(\mathcal{F}, \mathcal{D})$ fall into one of three categories: (1) non-extractable; (2) extractable with error $n^{-\Theta(1)}$; (3) extractable with error $2^{-\Omega(n)}$. This rules out other error rates like $1/\log n$ or $2^{-\sqrt{n}}$.

We provide essentially randomness-optimal extraction algorithms for extractable sources. Our algorithm for category (2) sources extracts with error $\epsilon$ from $n = \poly(1/\epsilon)$ samples in time linear in $n$. Our algorithm for category (3) sources extracts $m$ bits with error $\epsilon$ from $n = O(m + \log 1/\epsilon)$ samples in time $\min\{O(nm2^m),n^{O(|{\mathcal{F}}|)}\}$.

We also give algorithms for classifying a GSV source type $(\mathcal{F}, \mathcal{D})$: Membership in category (1) can be decided in $\mathrm{NP}$, while membership in category (3) is polynomial-time decidable.