“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16341
School of Mathematics
  Title:   Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources
  Author(s): 
1.  Sslmsn Beigi
2.  Omid Etesami (Joint with A. Bogdanov and S. Guo)
  Status:   In Proceedings
  Proceeding: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
  Year:  2018
  Pages:   DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.30
  Supported by:  IPM
  Abstract:
Let 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 minO(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.

Download TeX format
back to top
scroll left or right