Document Open Access Logo

Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources

Authors Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.30.pdf
  • Filesize: 445 kB
  • 15 pages

Document Identifiers

Author Details

Salman Beigi
  • Institute for Research in Fundamental Sciences, Tehran, Iran
Andrej Bogdanov
  • Chinese University of Hong Kong
Omid Etesami
  • Institute for Research in Fundamental Sciences, Tehran, Iran
Siyao Guo
  • Northeastern University, Boston, USA

Cite As Get BibTex

Salman Beigi, Andrej Bogdanov, Omid Etesami, and Siyao Guo. Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.30

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 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Expander graphs and randomness extractors
  • Mathematics of computing → Probability and statistics
  • Mathematics of computing → Information theory
Keywords
  • feasibility of randomness extraction
  • extractor lower bounds
  • martingales

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Salman Beigi, Andrej Bogdanov, Omid Etesami, and Siyao Guo. Complete classification of generalized Santha-Vazirani sources. Technical Report TR17-136, Electronic Colloquium on Computational Complexity, 2017. Google Scholar
  2. Salman Beigi, Omid Etesami, and Amin Gohari. Deterministic randomness extraction from generalized and distributed santha-vazirani sources. In International Colloquium on Automata, Languages, and Programming, pages 143-154. Springer, 2015. Google Scholar
  3. Salman Beigi, Omid Etesami, and Amin Gohari. Deterministic randomness extraction from generalized and distributed santha-vazirani sources. SIAM Journal on Computing, 46(1):1-36, 2017. Google Scholar
  4. Iddo Bentov, Ariel Gabizon, and David Zuckerman. Bitcoin beacon. arXiv preprint arXiv:1605.04559, 2016. Google Scholar
  5. Jean Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1(01):1-32, 2005. Google Scholar
  6. Jean Bourgain. On the construction of affine extractors. GAFA Geometric And Functional Analysis, 17(1):33-57, 2007. Google Scholar
  7. Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 670-683, 2016. URL: http://dx.doi.org/10.1145/2897518.2897528.
  8. Benny Chor and Oded Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17(2):230-261, 1988. Google Scholar
  9. Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran, and Amit Sahai. On the (im)possibility of cryptography with imperfect randomness. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 196-205, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.44.
  10. Zeev Dvir. Extractors for varieties. Computational complexity, 21(4):515-572, 2012. Google Scholar
  11. Zeev Dvir, Ariel Gabizon, and Avi Wigderson. Extractors and rank extractors for polynomial sources. Computational Complexity, 18(1):1-58, 2009. Google Scholar
  12. Ariel Gabizon. Deterministic extractors for affine sources over large fields. In Deterministic Extraction from Weak Random Sources, pages 33-53. Springer, 2011. Google Scholar
  13. Saeed Mahloujifar, Dimitrios I Diochnos, and Mohammad Mahmoody. Learning under p-tampering attacks. arXiv preprint arXiv:1711.03707, 2017. Google Scholar
  14. Saeed Mahloujifar and Mohammad Mahmoody. Blockwise p-tampering attacks on cryptographic primitives, extractors, and learners. In Theory of Cryptography Conference, pages 245-279. Springer, 2017. Google Scholar
  15. Jaikumar Radhakrishnan and Amnon Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discrete Math., 13(1):2-24, 2000. URL: http://dx.doi.org/10.1137/S0895480197329508.
  16. Miklos Santha and Umesh V. Vazirani. Generating quasi-random sequences from semi-random sources. J. Comput. Syst. Sci., 33(1):75-87, 1986. URL: http://dx.doi.org/10.1016/0022-0000(86)90044-9.
  17. Salil P Vadhan. Pseudorandomness, volume 56. Now, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact