Document Open Access Logo

Preserving Randomness for Adaptive Algorithms

Authors William M. Hoza , Adam R. Klivans

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.43.pdf
  • Filesize: 0.59 MB
  • 19 pages

Document Identifiers

Author Details

William M. Hoza
  • Department of Computer Science, University of Texas at Austin, Austin, TX, USA
Adam R. Klivans
  • Department of Computer Science, University of Texas at Austin, Austin, TX, USA

Funding

  • Hoza, William M.: Supported by the NSF GRFP under Grant DGE-1610403 and by a Harrington Fellowship from the University of Texas at Austin.

Cite As Get BibTex

William M. Hoza and Adam R. Klivans. Preserving Randomness for Adaptive Algorithms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 43:1-43:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.43

Abstract

Suppose Est is a randomized estimation algorithm that uses n random bits and outputs values in R^d. We show how to execute Est on k adaptively chosen inputs using only n + O(k log(d + 1)) random bits instead of the trivial nk (at the cost of mild increases in the error and failure probability). Our algorithm combines a variant of the INW pseudorandom generator [Impagliazzo et al., 1994] with a new scheme for shifting and rounding the outputs of Est. We prove that modifying the outputs of Est is necessary in this setting, and furthermore, our algorithm's randomness complexity is near-optimal in the case d <= O(1). As an application, we give a randomness-efficient version of the Goldreich-Levin algorithm; our algorithm finds all Fourier coefficients with absolute value at least theta of a function F: {0, 1}^n -> {-1, 1} using O(n log n) * poly(1/theta) queries to F and O(n) random bits (independent of theta), improving previous work by Bshouty et al. [Bshouty et al., 2004].

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • pseudorandomness
  • adaptivity
  • estimation

Metrics

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

Related Versions

References

  1. R. Armoni. On the derandomization of space-bounded computations. In Randomization and Approximation Techniques in Computer Science, pages 47-59. Springer, 1998. Google Scholar
  2. M. Bellare. A technique for upper bounding the spectral norm with applications to learning. In Proceedings of the 5th Annual Workshop on Computational Learning Theory, pages 62-70. ACM, 1992. Google Scholar
  3. N. H. Bshouty, J. C. Jackson, and C. Tamon. More efficient PAC-learning of DNF with membership queries under the uniform distribution. Journal of Computer and System Sciences, 68(1):205-234, 2004. Google Scholar
  4. H. Buhrman and L. Fortnow. One-sided versus two-sided error in probabilistic computation. In Annual Symposium on Theoretical Aspects of Computer Science, pages 100-109. Springer, 1999. Google Scholar
  5. Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM journal on computing, 38(1):97-139, 2008. Google Scholar
  6. C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. L. Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the 47th Annual Symposium on Theory of Computing, STOC '15, pages 117-126. ACM, 2015. Google Scholar
  7. E. Gat and S. Goldwasser. Probabilistic search algorithms with unique answers and their cryptographic applications. In Electronic Colloquium on Computational Complexity (ECCC), volume 18, page 136, 2011. Google Scholar
  8. O. Goldreich and L. A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, STOC '89, pages 25-32. ACM, 1989. Google Scholar
  9. O. Goldreich and A. Wigderson. Tiny families of functions with random properties: A quality-size trade-off for hashing. Random Structures &Algorithms, 11(4):315-343, 1997. URL: http://dx.doi.org/10.1002/(SICI)1098-2418(199712)11:4<315::AID-RSA3>3.0.CO;2-1.
  10. W. M. Hoza and A. R. Klivans. Preserving randomness for adaptive algorithms. arXiv preprint arXiv:1611.00783, 2016. Google Scholar
  11. R. Impagliazzo. Pseudo-random generators for cryptography and for randomized algorithms. PhD thesis, University of California, Berkeley, 1992. URL: http://cseweb.ucsd.edu/users/russell/format.ps.
  12. R. Impagliazzo, N. Nisan, and A. Wigderson. Pseudorandomness for network algorithms. In Proceedings of the 26th Annual Symposium on Theory of Computing, STOC '94, pages 356-364. ACM, 1994. Google Scholar
  13. R. Impagliazzo and D. Zuckerman. How to recycle random bits. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS '89, pages 248-253. IEEE, 1989. Google Scholar
  14. E. Kushilevitz and Y. Mansour. Learning decision trees using the Fourier spectrum. SIAM Journal on Computing, 22(6):1331-1348, 1993. Google Scholar
  15. L. A. Levin. Randomness and nondeterminism. Journal of Symbolic Logic, 58(3):1102-1103, 1993. Google Scholar
  16. P. Moser. Relative to p promise-bpp equals app. In Electronic Colloquium on Computational Complexity (ECCC) Report TR01, volume 68, 2001. Google Scholar
  17. J. Naor and M. Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM journal on computing, 22(4):838-856, 1993. Google Scholar
  18. N. Nisan and D. Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43-52, 1996. Google Scholar
  19. R. O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. Google Scholar
  20. R. Raz and O. Reingold. On recycling the randomness of states in space bounded computation. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, STOC '99, pages 159-168. ACM, 1999. URL: http://dx.doi.org/10.1145/301250.301294.
  21. M. Saks and S. Zhou. BP_H SPACE(S) ⊆ DSPACE(S^3/2). Journal of Computer and System Sciences, 58(2):376-403, 1999. Google Scholar
  22. S. 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