𝔖 Scriptorium
✦   LIBER   ✦

πŸ“

A primer on pseudorandom generators

✍ Scribed by Oded Goldreich


Publisher
American Mathematical Society
Year
2010
Tongue
English
Leaves
130
Series
University Lecture Series 055
Category
Library

⬇  Acquire This Volume

No coin nor oath required. For personal study only.

✦ Synopsis


A fresh look at the question of randomness was taken in the theory of computing: A distribution is pseudorandom if it cannot be distinguished from the uniform distribution by any efficient procedure. This paradigm, originally associating efficient procedures with polynomial-time algorithms, has been applied with respect to a variety of natural classes of distinguishing procedures. The resulting theory of pseudorandomness is relevant to science at large and is closely related to central areas of computer science, such as algorithmic design, complexity theory, and cryptography. This primer surveys the theory of pseudorandomness, starting with the general paradigm, and discussing various incarnations while emphasizing the case of general-purpose pseudorandom generators (withstanding any polynomial-time distinguisher). Additional topics include the "derandomization" of arbitrary probabilistic polynomial-time algorithms, pseudorandom generators withstanding space-bounded distinguishers, and several natural notions of special-purpose pseudorandom generators. The primer assumes basic familiarity with the notion of efficient algorithms and with elementary probability theory, but provides a basic introduction to all notions that are actually used. As a result, the primer is essentially self-contained, although the interested reader is at times referred to other sources for more detail

✦ Subjects


ΠœΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠ°;Π’Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠ°;


πŸ“œ SIMILAR VOLUMES


A Primer on Generative Adversarial Netwo
✍ Sanaa Kaddoura πŸ“‚ Library πŸ“… 2023 πŸ› Springer 🌐 English

<span>This book is meant for readers who want to understand GANs without the need for a strong mathematical background. Moreover, it covers the practical applications of GANs, making it an excellent resource for beginners.Β </span><span>A Primer on Generative Adversarial Networks</span><span>Β is suit

Using Hard Problems to Create Pseudorand
✍ Noam Nisan πŸ“‚ Library πŸ“… 1992 πŸ› The MIT Press 🌐 English

Randomization is an important tool in the design of algorithms, and the ability of randomization to provide enhanced power is a major research topic in complexity theory. Noam Nisan continues the investigation into the power of randomization and the relationships between randomized and deterministic

Using hard problems to create pseudorand
✍ Nisan N. πŸ“‚ Library πŸ“… 1992 πŸ› MIT 🌐 English

Randomization is an important tool in the design of algorithms, and the ability of randomization to provide enhanced power is a major research topic in complexity theory. Noam Nisan continues the investigation into the power of randomization and the relationships between randomized and deterministic