Name
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)$ $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 time linear $n$. Our algorithm for category (3) sources extracts $m$ bits with error $varepsilon$ from $n = O(m + log 1/varepsilon)$ samples time $min{O(nm2^m),n^{O(lvertmathcal{F}rvert)}}$. We also give algorithms for classifying a GSV source type $(mathcal{F}, mathcal{D})$: Membership category (1) can be decided $mathrm{NP}$, while membership category (3) is polynomial-time decidable. |
Year | Venue | Field |
|---|---|---|
2017 | Electronic Colloquium on Computational Complexity (ECCC) | Source type,Discrete mathematics,Combinatorics,Finite set,Decidability,Omega,Mathematics,Alphabet |
DocType | Volume | Citations |
Journal | 24 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Salman Beigi | 1 | 56 | 11.43 |
| Andrej Bogdanov | 2 | 458 | 31.53 |
| Omid Etesami | 3 | 120 | 9.85 |
| Siyao Guo | 4 | 50 | 5.01 |