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 $\epsilon$ from $n=\mathrm{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(nm{2}^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.

20 pages