Title: Complete Classification of Generalized Santha-Vazirani Sources,
Abstract: 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
$\varepsilon$ from $n = \mathrm{poly}(1/\varepsilon)$ samples in time linear in
$n$. Our algorithm for category (3) sources extracts $m$ bits with error
$\varepsilon$ from $n = O(m + \log 1/\varepsilon)$ samples in time
$\min\{O(nm2^m),n^{O(\lvert\mathcal{F}\rvert)}\}$.
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.