Document Open Access Logo

Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions

Authors Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.43.pdf
  • Filesize: 0.51 MB
  • 20 pages

Document Identifiers

Author Details

Avraham Ben-Aroya
  • The Blavatnik School of Computer Science, Tel-Aviv University, Tel Aviv, Israel
Gil Cohen
  • The Blavatnik School of Computer Science, Tel-Aviv University, Tel Aviv, Israel
Dean Doron
  • Department of Computer Science, University of Texas at Austin, USA
Amnon Ta-Shma
  • The Blavatnik School of Computer Science, Tel-Aviv University, Tel Aviv, Israel

Funding

  • Ben-Aroya, Avraham: Israel Science Foundation Grant 994/14 and by Len Blavatnik and the Blavatnik Family Foundation.
  • Doron, Dean: Israel Science Foundation Grant 994/14 and by Len Blavatnik and the Blavatnik Family Foundation. This work was done while being at Tel-Aviv University.
  • Ta-Shma, Amnon: Israel Science Foundation Grant 994/14.

Cite AsGet BibTex

Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma. Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 43:1-43:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.43

Abstract

In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error epsilon for n-bit sources having min-entropy {polylog}(n/epsilon). Unfortunately, the construction’s running-time is {poly}(n/epsilon), which means that with polynomial-time constructions, only polynomially-small errors are possible. Our main result is a {poly}(n,log(1/epsilon))-time computable two-source condenser. For any k >= {polylog}(n/epsilon), our condenser transforms two independent (n,k)-sources to a distribution over m = k-O(log(1/epsilon)) bits that is epsilon-close to having min-entropy m - o(log(1/epsilon)). Hence, achieving entropy gap of o(log(1/epsilon)). The bottleneck for obtaining low error in recent constructions of two-source extractors lies in the use of resilient functions. Informally, this is a function that receives input bits from r players with the property that the function’s output has small bias even if a bounded number of corrupted players feed adversarial inputs after seeing the inputs of the other players. The drawback of using resilient functions is that the error cannot be smaller than ln r/r. This, in return, forces the running time of the construction to be polynomial in 1/epsilon. A key component in our construction is a variant of resilient functions which we call entropy-resilient functions. This variant can be seen as playing the above game for several rounds, each round outputting one bit. The goal of the corrupted players is to reduce, with as high probability as they can, the min-entropy accumulated throughout the rounds. We show that while the bias decreases only polynomially with the number of players in a one-round game, their success probability decreases exponentially in the entropy gap they are attempting to incur in a repeated game.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Condensers
  • Extractors
  • Resilient functions
  • 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. M. Ajtai and N. Linial. The influence of large coalitions. Combinatorica, 13(2):129-145, 1993. Google Scholar
  3. N. Alon. The Shannon capacity of a union. Combinatorica, 18(3):301-310, 1998. Google Scholar
  4. N. Alon, O. Goldreich, and Y. Mansour. Almost k-wise independence versus k-wise independence. Information Processing Letters, 88(3):107-110, 2003. Google Scholar
  5. B. Barak. A simple explicit construction of an n^Õ(log n)-Ramsey graph. arXiv preprint, 2006. URL: http://arxiv.org/abs/math/0601651.
  6. B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson. Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. Journal of the ACM (JACM), 57(4):20, 2010. Google Scholar
  7. B. Barak, A. Rao, R. Shaltiel, and A. 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
  8. A. Ben-Aroya, E. Chattopadhyay, D. Doron, X. Li, and A. Ta-Shma. A New Approach for Constructing Low-Error, Two-Source Extractors. In LIPIcs-Leibniz International Proceedings in Informatics. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  9. A. Ben-Aroya, D. Doron, and A. Ta-Shma. An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1185-1194. ACM, 2017. Google Scholar
  10. A. Ben-Aroya, D. Doron, and A. Ta-Shma. Near-Optimal Erasure List-Decodable Codes. In Electronic Colloquium on Computational Complexity (ECCC), 2018. Google Scholar
  11. M. Ben-Or and N. Linial. Collective coin flipping, robust voting schemes and minima of Banzhaf values. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 408-416. IEEE, 1985. Google Scholar
  12. E. Ben-Sasson and N. Zewi. From affine to two-source extractors via approximate duality. In Proceedings of the 43rd annual ACM Symposium on Theory of computing (STOC), pages 177-186. ACM, 2011. Google Scholar
  13. J. 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
  14. M. Braverman. Polylogarithmic independence fools AC0 circuits. Journal of the ACM (JACM), 57(5):28, 2010. Google Scholar
  15. E. Chattopadhyay, V. Goyal, and X. Li. Non-malleable extractors and codes, with their many tampered extensions. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 285-298. ACM, 2016. Google Scholar
  16. E. Chattopadhyay and X. Li. Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 158-167. IEEE, 2016. Google Scholar
  17. E. Chattopadhyay and D. 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
  18. B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17(2):230-261, 1988. Google Scholar
  19. F. R. K. Chung. A note on constructive methods for Ramsey numbers. Journal of Graph Theory, 5(1):109-113, 1981. Google Scholar
  20. G. Cohen. Local correlation breakers and applications to three-source extractors and mergers. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 845-862. IEEE, 2015. Google Scholar
  21. G. Cohen. Making the Most of Advice: New Correlation Breakers and Their Applications. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 188-196. IEEE, 2016. Google Scholar
  22. G. Cohen. Two-source extractors for quasi-logarithmic min-entropy and improved privacy amplification protocols. In Electronic Colloquium on Computational Complexity (ECCC), 2016. Google Scholar
  23. G. Cohen. Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 278-284. ACM, 2016. Google Scholar
  24. G. Cohen and L. Schulman. Extractors for Near Logarithmic Min-Entropy. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), page 14, 2016. Google Scholar
  25. P. Frankl. A constructive lower bound for Ramsey numbers. Ars Combinatoria, 3(297-302):28, 1977. Google Scholar
  26. P. Frankl and R. M. Wilson. Intersection theorems with geometric consequences. Combinatorica, 1(4):357-368, 1981. Google Scholar
  27. V. Grolmusz. Low rank co-diagonal matrices and Ramsey graphs. Journal of combinatorics, 7(1):R15-R15, 2001. Google Scholar
  28. V. Guruswami, C. Umans, and S. Vadhan. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Journal of the ACM, 56(4):20, 2009. Google Scholar
  29. P. Harsha and S. Srinivasan. On Polynomial Approximations to AC0. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2016. Google Scholar
  30. K. Kahn, G. Kalai, and N. Linial. The influence of variables on Boolean functions. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 68-80. IEEE, 1988. Google Scholar
  31. Mark Lewko. An explicit two-source extractor with min-entropy near 4/9. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.05451.
  32. X. Li. Extractors for a constant number of independent sources with polylogarithmic min-entropy. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 100-109, 2013. Google Scholar
  33. X. Li. New independent source extractors with exponential improvement. In Proceedings of the 45th annual ACM Symposium on Theory of Computing (STOC), pages 783-792. ACM, 2013. Google Scholar
  34. X. Li. Three-source extractors for polylogarithmic min-entropy. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 863-882. IEEE, 2015. Google Scholar
  35. X. Li. Improved non-malleable extractors, non-malleable codes and independent source extractors. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1144-1156. ACM, 2017. Google Scholar
  36. X. Li. Non-malleable extractors and non-malleable codes: Partially optimal constructions. In Electronic Colloquium on Computational Complexity (ECCC), 2018. Google Scholar
  37. R. 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
  38. Zs. Nagy. A constructive estimation of the Ramsey numbers. Mat. Lapok, 23:301-302, 1975. Google Scholar
  39. M. Naor. Constructing Ramsey graphs from small probability spaces. IBM Research Report RJ, 8810, 1992. Google Scholar
  40. A. Rao. A 2-source almost-extractor for linear entropy. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 549-556. Springer, 2008. Google Scholar
  41. A. Rao. Extractors for a constant number of polynomially small min-entropy independent sources. SIAM Journal on Computing, 39(1):168-194, 2009. Google Scholar
  42. R. 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
  43. R. Raz, O. Reingold, and S. Vadhan. Error reduction for extractors. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 191-201. IEEE, 1999. Google Scholar
  44. A. Tal. Tight bounds on the Fourier spectrum of AC0. In LIPIcs-Leibniz International Proceedings in Informatics, volume 79. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  45. John von Neumann. Various techniques used in connection with random digits. John von Neumann, Collected Works, 5:768-770, 1963. Google Scholar
  46. D. Zuckerman. Randomness-optimal oblivious sampling. Random Structures and Algorithms, 11(4):345-367, 1997. Google Scholar
  47. D. Zuckerman. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing, 3:103-128, 2007. 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