Document Open Access Logo

A New Approach for Constructing Low-Error, Two-Source Extractors

Authors Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma

PDF
Thumbnail PDF

File

LIPIcs.CCC.2018.3.pdf
  • Filesize: 0.54 MB
  • 19 pages

Document Identifiers

Author Details

Avraham Ben-Aroya
  • The Blavatnik School of Computer Science, Tel-Aviv University, Tel Aviv 69978, Israel
Eshan Chattopadhyay
  • Department of Computer Science, Cornell University and School of Mathematics, IAS, Ithaca, NY 14850, USA
  • Princeton, NJ 08540, USA
Dean Doron
  • The Blavatnik School of Computer Science, Tel-Aviv University, Tel Aviv 69978, Israel
Xin Li
  • Department of Computer Science, Johns Hopkins University, Baltimore, MD 21218, USA
Amnon Ta-Shma
  • The Blavatnik School of Computer Science, Tel-Aviv University, Tel Aviv 69978, Israel

Funding

  • Ben-Aroya, Avraham: Supported by the Israel Science Foundation grant no. 994/14.
  • Chattopadhyay, Eshan: Supported by NSF grants CCF-1526952, CCF-1412958 and the Simons Foundation. Part of this work was done when the author was a graduate student in UT Austin and while visiting the Simons Institute for the Theory of Computing at UC Berkeley.
  • Doron, Dean: Supported by the Israel Science Foundation grant no. 994/14. This work was done in part while visiting the Simons Institute for the Theory of Computing at UC Berkeley.
  • Li, Xin: Supported by NSF Grant CCF-1617713.
  • Ta-Shma, Amnon: Supported by the Israel Science Foundation grant no. 994/14. This work was done in part while visiting the Simons Institute for the Theory of Computing at UC Berkeley.

Cite AsGet BibTex

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, and Amnon Ta-Shma. A New Approach for Constructing Low-Error, Two-Source Extractors. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.CCC.2018.3

Abstract

Our main contribution in this paper is a new reduction from explicit two-source extractors for polynomially-small entropy rate and negligible error to explicit t-non-malleable extractors with seed-length that has a good dependence on t. Our reduction is based on the Chattopadhyay and Zuckerman framework (STOC 2016), and surprisingly we dispense with the use of resilient functions which appeared to be a major ingredient there and in follow-up works. The use of resilient functions posed a fundamental barrier towards achieving negligible error, and our new reduction circumvents this bottleneck. The parameters we require from t-non-malleable extractors for our reduction to work hold in a non-explicit construction, but currently it is not known how to explicitly construct such extractors. As a result we do not give an unconditional construction of an explicit low-error two-source extractor. Nonetheless, we believe our work gives a viable approach for solving the important problem of low-error two-source extractors. Furthermore, our work highlights an existing barrier in constructing low-error two-source extractors, and draws attention to the dependence of the parameter t in the seed-length of the non-malleable extractor. We hope this work would lead to further developments in explicit constructions of both non-malleable and two-source extractors.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Two-Source Extractors
  • Non-Malleable Extractors
  • Pseudorandomness
  • Explicit Constructions

Metrics

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

References

  1. H.L. Abbott. Lower bounds for some Ramsey numbers. Discrete Mathematics, 2(4):289-293, 1972. Google Scholar
  2. Noga Alon. The Shannon capacity of a union. Combinatorica, 18(3):301-310, 1998. Google Scholar
  3. Boaz Barak. A simple explicit construction of an n^õ(log n)-Ramsey graph. arXiv preprint math/0601651, 2006. Google Scholar
  4. Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, and Avi Wigderson. Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. Journal of the ACM (JACM), 57(4):20, 2010. Google Scholar
  5. Boaz Barak, Anup Rao, Ronen Shaltiel, and Avi Wigderson. 2-source dispersers for n^o(1) entropy, and Ramsey graphs beating the frankl-wilson construction. Annals of Mathematics, 176(3):1483-1544, 2012. Google Scholar
  6. Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), pages 1185-1194. ACM, 2017. Google Scholar
  7. 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
  8. Eshan Chattopadhyay, Vipul Goyal, and Xin Li. Non-malleable extractors and codes, with their many tampered extensions. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 285-298. ACM, 2016. Google Scholar
  9. Eshan Chattopadhyay and Xin Li. Explicit non-malleable extractors, multi-source extractors, and almost optimal privacy amplification protocols. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 158-167. IEEE, 2016. Google Scholar
  10. Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 670-683. ACM, 2016. Google Scholar
  11. 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
  12. Fan R.K. Chung. A note on constructive methods for Ramsey numbers. Journal of Graph Theory, 5(1):109-113, 1981. Google Scholar
  13. Gil Cohen. Local correlation breakers and applications to three-source extractors and mergers. SIAM Journal on Computing, 45(4):1297-1338, 2016. Google Scholar
  14. Gil Cohen. Making the most of advice: New correlation breakers and their applications. In Proceedings of 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 188-196. IEEE, 2016. Google Scholar
  15. Gil Cohen. Non-malleable extractors - new tools and improved constructions. In LIPIcs-Leibniz International Proceedings in Informatics, volume 50. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  16. Gil Cohen. Non-malleable extractors with logarithmic seeds. In Electronic Colloquium on Computational Complexity (ECCC), volume 23, page 30, 2016. Google Scholar
  17. Gil Cohen. Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 278-284. ACM, 2016. Google Scholar
  18. Gil Cohen. Two-source extractors for quasi-logarithmic min-entropy and improved privacy amplification protocols. In ECCC, 2016. Google Scholar
  19. Gil Cohen, Ran Raz, and Gil Segev. Nonmalleable extractors with short seeds and applications to privacy amplification. SIAM Journal on Computing, 43(2):450-476, 2014. Google Scholar
  20. Gil Cohen and Igor Shinkar. Personal communication, 2017. Google Scholar
  21. Yevgeniy Dodis and Daniel Wichs. Non-malleable extractors and symmetric key cryptography from weak secrets. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 601-610. ACM, 2009. Google Scholar
  22. Peter Frankl. A constructive lower bound for ramsey numbers. Ars Combinatoria, 3(297-302):28, 1977. Google Scholar
  23. Peter Frankl and Richard M. Wilson. Intersection theorems with geometric consequences. Combinatorica, 1(4):357-368, 1981. Google Scholar
  24. Vince Grolmusz. Low rank co-diagonal matrices and Ramsey graphs. Journal of combinatorics, 7(1):R15-R15, 2001. Google Scholar
  25. Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on boolean functions. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS), pages 68-80. IEEE, 1988. Google Scholar
  26. Xin Li. Non-malleable extractors, two-source extractors and privacy amplification. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 688-697. IEEE, 2012. Google Scholar
  27. Xin Li. Improved two-source extractors, and affine extractors for polylogarithmic entropy. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 168-177. IEEE, 2016. Google Scholar
  28. Xin Li. Improved non-malleable extractors, non-malleable codes and independent source extractors. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1144-1156. ACM, 2017. URL: http://dx.doi.org/10.1145/3055399.3055486.
  29. Raghu Meka. Explicit resilient functions matching ajtai-linial. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1132-1148. SIAM, 2017. Google Scholar
  30. Zs Nagy. A constructive estimation of the ramsey numbers. Mat. Lapok, 23:301-302, 1975. Google Scholar
  31. Moni Naor. Constructing Ramsey graphs from small probability spaces. IBM Research Report RJ, 8810, 1992. Google Scholar
  32. Victor Neumann-Lara. The dichromatic number of a digraph. Journal of Combinatorial Theory, Series B, 33(3):265-270, 1982. Google Scholar
  33. Jaikumar Radhakrishnan and Amnon Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Discrete Mathematics, 13(1):2-24, 2000. Google Scholar
  34. Ran Raz. Extractors with weak random seeds. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 11-20. ACM, 2005. Google Scholar
  35. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 681-690. ACM, 2006. 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 Imprint Privacy Contact