ECCC-Report TR17-136https://eccc.weizmann.ac.il/report/2017/136Comments and Revisions published for TR17-136en-usSun, 10 Sep 2017 17:39:14 +0300
Paper TR17-136
| Complete Classification of Generalized Santha-Vazirani Sources |
Omid Etesami,
Andrej Bogdanov,
Salman Beigi,
Siyao Guo
https://eccc.weizmann.ac.il/report/2017/136Let $\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.Sun, 10 Sep 2017 17:39:14 +0300https://eccc.weizmann.ac.il/report/2017/136