Article

How to recycle random bits

Authors:

R. Impagliazzo,

D. ZuckermanAuthors Info & Claims

SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer Science

Pages 248 - 253

https://doi.org/10.1109/SFCS.1989.63486

Published: 30 October 1989 Publication History

Publisher Site

Abstract

It is shown that modified versions of the linear congruential generator and the shift register generator are provably good for amplifying the correctness of a probabilistic algorithm. More precisely, if r random bits are needed for a BPP algorithm to be correct with probability at least 2/3, then O(r+k/sup 2/) bits are needed to improve this probability to 1-2/sup -k/. A different pseudorandom generator that is optimal, up to a constant factor, in this regard is also presented. It uses only O(r+k) bits to improve the probability to 1-2/sup -k/. This generator is based on random walks on expanders. The results do not depend on any unproven assumptions. It is shown that the modified versions of the shift register and linear congruential generators can be used to sample from distributions using, in the limit, the information-theoretic lower bound on random bits.

Cited By

View all

Watson T(2020)Quadratic Simulations of Merlin–Arthur GamesACM Transactions on Computation Theory10.1145/338939912:2(1-11)Online publication date: 3-May-2020
https://dl.acm.org/doi/10.1145/3389399
Balle BBell JGascón ANissim KLigatti JOu XKatz JVigna G(2020)Private Summation in the Multi-Message Shuffle ModelProceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security10.1145/3372297.3417242(657-676)Online publication date: 30-Oct-2020
https://dl.acm.org/doi/10.1145/3372297.3417242
Lindell YZarosim H(2018)On the Feasibility of Extending Oblivious TransferJournal of Cryptology10.1007/s00145-017-9269-531:3(737-773)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s00145-017-9269-5
Show More Cited By

Index Terms

How to recycle random bits
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods

Index terms have been assigned to the content through auto-classification.

Recommendations

On the lattice structure of the add-with-carry and subtract-with-borrow random number generators

Marsaglia and Zaman recently proposed new classes of random number generators, called add-with-carry(AWC) and subtract-with-borrow(SWB), which are capable of quickly generating very long-period (pseudo)-random number sequences using very little memory. ...
General weak random sources
SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer Science

The following model for a weak random source is considered. The source is asked only once for R bits, and the source outputs an R-bit string such that no string has probability more than 2/sup - delta R/ of being output. for some fixed delta >0. A ...
A note on the quality of random variates generated by the ratio of uniforms method

The one-dimensional distribution of pseudorandom numbers generated by the ratio of uniforms method using linear congruential generators (LCGs) as the source of uniform random number is investigated in this note. Due to the two-dimensional lattice ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer Science

October 1989

586 pages

ISBN:0818619821

Publisher

IEEE Computer Society

United States

Publication History

Published: 30 October 1989

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

67
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Watson T(2020)Quadratic Simulations of Merlin–Arthur GamesACM Transactions on Computation Theory10.1145/338939912:2(1-11)Online publication date: 3-May-2020
https://dl.acm.org/doi/10.1145/3389399
Balle BBell JGascón ANissim KLigatti JOu XKatz JVigna G(2020)Private Summation in the Multi-Message Shuffle ModelProceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security10.1145/3372297.3417242(657-676)Online publication date: 30-Oct-2020
https://dl.acm.org/doi/10.1145/3372297.3417242
Lindell YZarosim H(2018)On the Feasibility of Extending Oblivious TransferJournal of Cryptology10.1007/s00145-017-9269-531:3(737-773)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s00145-017-9269-5
Acharya JOrlitsky ASuresh ATyagi H(2017)Estimating Renyi Entropy of Discrete DistributionsIEEE Transactions on Information Theory10.1109/TIT.2016.262043563:1(38-56)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TIT.2016.2620435
Yu YSteinberger J(2016)Pseudorandom Functions in Almost Constant Depth from Low-Noise LPNProceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 966610.5555/3081738.3081744(154-183)Online publication date: 8-May-2016
https://dl.acm.org/doi/10.5555/3081738.3081744
Chen SDippel MRussell ASamanta ASundaram R(2016)Markovian hitters and the complexity of blind rendezvousProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884480(610-619)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884480
Prakash NTyagi H(2016)Multiterminal Secrecy by Public DiscussionFoundations and Trends in Communications and Information Theory10.1561/010000007213:2-3(129-275)Online publication date: 28-Sep-2016
https://dl.acm.org/doi/10.1561/0100000072
Canonne CGouleakis TRubinfeld RSudan M(2016)Sampling CorrectorsProceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science10.1145/2840728.2840729(93-102)Online publication date: 14-Jan-2016
https://dl.acm.org/doi/10.1145/2840728.2840729
Acharya JOrlitsky ASuresh ATyagi HIndyk P(2015)The complexity of estimating Rényi entropyProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722253(1855-1869)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722253
Valiant G(2015)Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair ProblemJournal of the ACM10.1145/272816762:2(1-45)Online publication date: 6-May-2015
https://dl.acm.org/doi/10.1145/2728167
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

On the lattice structure of the add-with-carry and subtract-with-borrow random number generators

General weak random sources

A note on the quality of random variates generated by the ratio of uniforms method

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations