Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources
Refereed conference paper presented and published in conference proceedings


Full Text

Times Cited

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

We show that all GSV source types (F, D) fall into one of three categories: (1) non-extractable; (2) extractable with error n^{-Theta(1)}; (3) extractable with error 2^{-Omega(n)}.

We provide essentially randomness-optimal extraction algorithms for extractable sources. Our algorithm for category (2) sources extracts one bit 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(m2^m * n),n^{O(|F|)}}.
We also give algorithms for classifying a GSV source type (F, D): Membership in category (1) can be decided in NP, while membership in category (3) is polynomial-time decidable.
All Author(s) ListSalman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo
Name of Conference22nd International Conference on Randomization and Computation (RANDOM'2018)
Start Date of Conference20/08/2018
End Date of Conference22/08/2018
Place of ConferencePrinceton, NJ
Country/Region of ConferenceUnited States of America
Proceedings TitleLeibniz International Proceedings in Informatics, LIPIcs
Year2018
Month8
Volume Number116
Article number30
ISBN978-3-95977-085-9
LanguagesEnglish-United States

Last updated on 2021-06-12 at 23:33