Document Open Access Logo

Samplers and Extractors for Unbounded Functions

Author Rohit Agrawal

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.59.pdf
  • Filesize: 0.54 MB
  • 21 pages

Document Identifiers

Author Details

Rohit Agrawal
  • John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA

Funding

  • Agrawal, Rohit: Supported by the Department of Defense (DoD) through the National Defense Science & Engineering Graduate Fellowship (NDSEG) Program.

Acknowledgements

The author would like to thank Jarosław Błasiok for suggesting the problem of constructing subgaussian samplers and for helpful discussions and feedback, Salil Vadhan for many helpful discussions and his detailed feedback on this writeup, and the anonymous reviewers for their helpful comments and feedback.

Cite As Get BibTex

Rohit Agrawal. Samplers and Extractors for Unbounded Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 59:1-59:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.59

Abstract

Błasiok (SODA'18) recently introduced the notion of a subgaussian sampler, defined as an averaging sampler for approximating the mean of functions f from {0,1}^m to the real numbers such that f(U_m) has subgaussian tails, and asked for explicit constructions. In this work, we give the first explicit constructions of subgaussian samplers (and in fact averaging samplers for the broader class of subexponential functions) that match the best known constructions of averaging samplers for [0,1]-bounded functions in the regime of parameters where the approximation error epsilon and failure probability delta are subconstant. Our constructions are established via an extension of the standard notion of randomness extractor (Nisan and Zuckerman, JCSS'96) where the error is measured by an arbitrary divergence rather than total variation distance, and a generalization of Zuckerman’s equivalence (Random Struct. Alg.'97) between extractors and samplers. We believe that the framework we develop, and specifically the notion of an extractor for the Kullback-Leibler (KL) divergence, are of independent interest. In particular, KL-extractors are stronger than both standard extractors and subgaussian samplers, but we show that they exist with essentially the same parameters (constructively and non-constructively) as standard extractors.

Subject Classification

ACM Subject Classification
  • Theory of computation → Expander graphs and randomness extractors
  • Theory of computation → Pseudorandomness and derandomization
  • Mathematics of computing → Information theory
Keywords
  • averaging samplers
  • subgaussian samplers
  • randomness extractors
  • Kullback-Leibler divergence

Metrics

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

Related Versions

References

  1. Rohit Agrawal. Samplers and Extractors for Unbounded Functions. arXiv:1904.08391 [cs], July 2019. URL: http://arxiv.org/abs/1904.08391.
  2. Syed Mumtaz Ali and Samuel David Silvey. A General Class of Coefficients of Divergence of One Distribution from Another. Journal of the Royal Statistical Society. Series B (Methodological), 28(1):131-142, 1966. Google Scholar
  3. Koenraad M. R. Audenaert and Jens Eisert. Continuity Bounds on the Quantum Relative Entropy. Journal of Mathematical Physics, 46(10):102104, October 2005. URL: https://doi.org/10.1063/1.2044667.
  4. Boaz Barak, Yevgeniy Dodis, Hugo Krawczyk, Olivier Pereira, Krzysztof Pietrzak, François-Xavier Standaert, and Yu Yu. Leftover Hash Lemma, Revisited. In Phillip Rogaway, editor, Advances in Cryptology endash CRYPTO 2011, Lecture Notes in Computer Science, pages 1-20. Springer Berlin Heidelberg, 2011. Google Scholar
  5. Mihir Bellare, Oded Goldreich, and Shafi Goldwasser. Randomness in Interactive Proofs. computational complexity, 3(4):319-354, December 1993. URL: https://doi.org/10.1007/BF01275487.
  6. Mihir Bellare and John Rompel. Randomness-Efficient Oblivious Sampling. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 276-287, November 1994. URL: https://doi.org/10.1109/SFCS.1994.365687.
  7. Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert. Privacy Amplification by Public Discussion. SIAM Journal on Computing, 17(2):210-229, April 1988. URL: https://doi.org/10.1137/0217014.
  8. Jarosław Błasiok. Private Communication, 2018. Google Scholar
  9. Jarosław Błasiok. Optimal Streaming and Tracking Distinct Elements with High Probability. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, pages 2432-2448. Society for Industrial and Applied Mathematics, January 2018. URL: https://doi.org/10.1137/1.9781611975031.156.
  10. Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 1 edition edition, February 2013. URL: https://doi.org/10.1093/acprof:oso/9780199535255.001.0001.
  11. Ran Canetti, Guy Even, and Oded Goldreich. Lower Bounds for Sampling Algorithms for Estimating the Average. Information Processing Letters, 53(1):17-25, January 1995. URL: https://doi.org/10.1016/0020-0190(94)00171-T.
  12. Benny Chor and Oded Goldreich. On the Power of Two-Point Based Sampling. Journal of Complexity, 5(1):96-106, March 1989. URL: https://doi.org/10.1016/0885-064X(89)90015-0.
  13. Imre Csiszár. Eine Informationstheoretische Ungleichung Und Ihre Anwendung Auf Den Beweis Der Ergodizität von Markoffschen Ketten. Magyar Tud. Akad. Mat. Kutató Int. Közl., 8:85-108, 1963. Google Scholar
  14. Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM Journal on Computing, 38(1):97-139, January 2008. URL: https://doi.org/10.1137/060651380.
  15. Monroe D. Donsker and S. R. Srinivasa Varadhan. Asymptotic Evaluation of Certain Markov Process Expectations for Large TimeemdashIII. Communications on Pure and Applied Mathematics, 29(4):389-461, 1976. URL: https://doi.org/10.1002/cpa.3160290405.
  16. David Gillman. A Chernoff Bound for Random Walks on Expander Graphs. SIAM Journal on Computing, 27(4):1203-1220, August 1998. URL: https://doi.org/10.1137/S0097539794268765.
  17. Oded Goldreich. A Sample of Samplers: A Computational Perspective on Sampling. In Oded Goldreich, editor, Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, Lecture Notes in Computer Science, pages 302-332. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. URL: https://doi.org/10.1007/978-3-642-22670-0_24.
  18. Oded Goldreich and Salil Vadhan. Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK. In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, pages 54-73, May 1999. URL: https://doi.org/10.1109/CCC.1999.766262.
  19. Oded Goldreich and Avi Wigderson. Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing. Random Structures & Algorithms, 11(4):315-343, 1997. URL: https://doi.org/10.1002/(SICI)1098-2418(199712)11:4<315::AID-RSA3>3.0.CO;2-1.
  20. Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. Unbalanced Expanders and Randomness Extractors from ParvareshendashVardy Codes. Journal of the ACM, 56(4):20:1-20:34, July 2009. URL: https://doi.org/10.1145/1538902.1538904.
  21. Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Pseudo-Random Generation from One-Way Functions. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC '89, pages 12-24, New York, NY, USA, 1989. ACM. URL: https://doi.org/10.1145/73007.73009.
  22. Richard Karp, Nicholas Pippenger, and Michael Sipser. A Time-Randomness Tradeoff. In AMS Conference on Probabilistic Computational Complexity, Durham, New Hampshire, 1985. Google Scholar
  23. James Lawrence McInnes. Cryptography Using Weak Sources of Randomness. Technical Report 194/87, University of Toronto, 1987. Google Scholar
  24. Tetsuzo Morimoto. Markov Processes and the H-Theorem. Journal of the Physical Society of Japan, 18(3):328-331, March 1963. URL: https://doi.org/10.1143/JPSJ.18.328.
  25. Alfred Müller. Integral Probability Metrics and Their Generating Classes of Functions. Advances in Applied Probability, 29(2):429-443, 1997. URL: https://doi.org/10.2307/1428011.
  26. Noam Nisan and David Zuckerman. Randomness Is Linear in Space. Journal of Computer and System Sciences, 52(1):43-52, February 1996. URL: https://doi.org/10.1006/jcss.1996.0004.
  27. Jaikumar Radhakrishnan and Amnon Ta-Shma. Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators. SIAM Journal on Discrete Mathematics, 13(1):2-24, January 2000. URL: https://doi.org/10.1137/S0895480197329508.
  28. Ran Raz, Omer Reingold, and Salil Vadhan. Extracting All the Randomness and Reducing the Error in Trevisan’s Extractors. Journal of Computer and System Sciences, 65(1):97-128, August 2002. URL: https://doi.org/10.1006/jcss.2002.1824.
  29. Omer Reingold, Luca Trevisan, Madhur Tulsiani, and Salil Vadhan. New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition. arXiv:0806.0381 [math], June 2008. URL: http://arxiv.org/abs/0806.0381.
  30. Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 3-13, November 2000. URL: https://doi.org/10.1109/SFCS.2000.892006.
  31. Alfréd Rényi. On Measures of Entropy and Information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics. The Regents of the University of California, 1961. Google Scholar
  32. Ofer Shayevitz. On Rényi Measures and Hypothesis Testing. In 2011 IEEE International Symposium on Information Theory Proceedings, pages 894-898, July 2011. URL: https://doi.org/10.1109/ISIT.2011.6034266.
  33. Aravind Srinivasan and David Zuckerman. Computing with Very Weak Random Sources. SIAM Journal on Computing, 28(4):1433-1459, January 1999. URL: https://doi.org/10.1137/S009753979630091X.
  34. Amnon Ta-Shma, David Zuckerman, and Shmuel Safra. Extractors from ReedendashMuller Codes. Journal of Computer and System Sciences, 72(5):786-812, August 2006. URL: https://doi.org/10.1016/j.jcss.2005.05.010.
  35. Salil P. Vadhan. Pseudorandomness. Now Publishers Inc, Boston, Mass., October 2012. Google Scholar
  36. Tim van Erven. When Data Compression and Statistics Disagree: Two Frequentist Challenges for the Minimum Description Length Principle. PhD thesis, Leiden University, 2010. OCLC: 673140651. Google Scholar
  37. Tim van Erven and Peter Harremoës. Rényi Divergence and Kullback-Leibler Divergence. IEEE Transactions on Information Theory, 60(7):3797-3820, July 2014. URL: https://doi.org/10.1109/TIT.2014.2320500.
  38. Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Number 47 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2018. Google Scholar
  39. Vladimir Mikhailovich Zolotarev. Probability Metrics. Theory of Probability & Its Applications, 28(2):278-302, January 1984. URL: https://doi.org/10.1137/1128025.
  40. David Zuckerman. Randomness-Optimal Oblivious Sampling. Random Structures & Algorithms, 11(4):345-367, 1997. URL: https://doi.org/10.1002/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z.
  41. David Zuckerman. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing, 3(1):103-128, August 2007. URL: https://doi.org/10.4086/toc.2007.v003a006.
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