Pseudorandomness (Q2869768)

The monograph under review gives a deep and comprehensive introduction to the area of pseudorandomness. This area is concerned with the generation of objects that ``look random'' despite being deterministic or generated with only little randomness. Such pseudorandom constructions found numerous applications in many different areas, e.g., complexity theory, algorithms, combinatorics, and number theory.NEWLINENEWLINEThe text consists of 8 chapters.NEWLINENEWLINEThe short introduction introduces the topic, makes its importance clear, and gives on an easy-to-digest level several key examples of pseudorandom objects.NEWLINENEWLINEIt makes little sense to study pseudorandomness without knowing the basic uses of randomness in computer science and discrete mathematics. The second chapter thus gives a concise introduction to various applications of randomness in computer science. Like the rest of the monograph, it assumes very little previous knowledge from the reader, so it can be recommended as a beautiful introduction to randomized methods in computer science also to an audience beyond those interested in pseudorandomness in particular.NEWLINENEWLINESome elementary ways to reduce or fully avoid randomness, usually called derandomizations, are discussed in the third chapter. They incluce the classic method of conditional probabilities.NEWLINENEWLINEChapters four to seven each discusses in detail a particular pseudorandom object. The fourth chapter starts with the important notion of an expander graph. These are graphs that are well-connected despite having only a small number of edges. The chapter discusses different notions of expansion, the behavior of random walks on expander graphs, some explicit constructions of exander graphs, and finally proves Reingold's famous result that \(s\)-\(t\) connectivity can be decided deterministically in logarithmic space.NEWLINENEWLINEThe fifth chapter is devoted to coding theory, in particular, to list-decodable codes. The chapter starts with a concise introduction to coding theory and list-decodable codes. Then a number of codes allowing efficient list-decoding are introduced. Finally, several connections between the seemingly unrelated topics of expander graphs and list-decoding are discussed.NEWLINENEWLINEThe topic of the sixth chapter are randomness extractors -- functions that produce (ideally) independent random bits from much weaker sources of randomness. Connections to hash functions, expanders, and list-decoding are given. Finally, an extractor optimal apart from constant factors is constructed.NEWLINENEWLINEThe last of the four ``pseudorandom objects'' chapters treats pseudorandom generators. Here the objective is to take few perfectly random independent bits and generate from them a much longer sequence of random bits that is, obviously, not uniformly distributed, but that is hard to distinguish from a truly uniform random bit string.NEWLINENEWLINEFinally, the eighth chapter gives a summary and strengthens the monograph's main message that pseudorandomness is not only a collection of different very useful objects, but that these objects are strongly connected despite being from very different application areas.NEWLINENEWLINEThis monograph is both a great text for a graduate course or for self-study and a substantial research monograph. With not much previous knowledge required and several exercises in each chapter, it is a perfect choice for a newcomer to this area. With its over 400 references, the experienced researcher will be equally happy to have this monograph on the bookshelf.