Softcover ISBN:  9780821851920 
Product Code:  ULECT/55 
List Price:  $41.00 
MAA Member Price:  $36.90 
AMS Member Price:  $32.80 
Electronic ISBN:  9781470416508 
Product Code:  ULECT/55.E 
List Price:  $38.00 
MAA Member Price:  $34.20 
AMS Member Price:  $30.40 

Book DetailsUniversity Lecture SeriesVolume: 55; 2010; 114 ppMSC: Primary 68;
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 polynomialtime 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 generalpurpose pseudorandom generators (withstanding any polynomialtime distinguisher). Additional topics include the “derandomization” of arbitrary probabilistic polynomialtime algorithms, pseudorandom generators withstanding spacebounded distinguishers, and several natural notions of specialpurpose 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 selfcontained, although the interested reader is at times referred to other sources for more detail.ReadershipAdvanced undergraduates and computer science majors, graduate students, and research mathematicians interested in complexity theory; cryptography; and pseudorandom generators.

Table of Contents

Chapters

Chapter 1. Introduction

Chapter 2. Generalpurpose pseudorandom generators

Chapter 3. Derandomization of timecomplexity classes

Chapter 4. Spacebounded distinguishers

Chapter 5. Special purpose generators

Concluding remarks

Appendix A. Hashing functions

Appendix B. On randomness extractors

Appendix C. A generic hardcore predicate

Appendix D. Using randomness in computation

Appendix E. Cryptographic applications of pseudorandom functions

Appendix F. Some basic complexity classes


Additional Material

Reviews

This book provides basic information about pseudorandom generators, one of the topics with the strongest impact in recent years, not only because of the subject itself but also because of its many applications in all fields of science.
Luis Hernandez Encinas, Mathematical Reviews


RequestsReview Copy – for reviewers who would like to review an AMS bookPermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Additional Material
 Reviews
 Requests
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 polynomialtime 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 generalpurpose pseudorandom generators (withstanding any polynomialtime distinguisher). Additional topics include the “derandomization” of arbitrary probabilistic polynomialtime algorithms, pseudorandom generators withstanding spacebounded distinguishers, and several natural notions of specialpurpose 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 selfcontained, although the interested reader is at times referred to other sources for more detail.
Advanced undergraduates and computer science majors, graduate students, and research mathematicians interested in complexity theory; cryptography; and pseudorandom generators.

Chapters

Chapter 1. Introduction

Chapter 2. Generalpurpose pseudorandom generators

Chapter 3. Derandomization of timecomplexity classes

Chapter 4. Spacebounded distinguishers

Chapter 5. Special purpose generators

Concluding remarks

Appendix A. Hashing functions

Appendix B. On randomness extractors

Appendix C. A generic hardcore predicate

Appendix D. Using randomness in computation

Appendix E. Cryptographic applications of pseudorandom functions

Appendix F. Some basic complexity classes

This book provides basic information about pseudorandom generators, one of the topics with the strongest impact in recent years, not only because of the subject itself but also because of its many applications in all fields of science.
Luis Hernandez Encinas, Mathematical Reviews