Pseudorandomness
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Decoding (94B35)
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.
- Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries
- Stabilizing network bargaining games by blocking players
- Public-coin statistical zero-knowledge batch verification against malicious verifiers
- Constructing locally leakage-resilient linear secret-sharing schemes
- Derandomizing local distributed algorithms under bandwidth restrictions
- Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors
- Lossless dimension expanders via linearized polynomials and subspace designs
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- New techniques and tighter bounds for local computation algorithms
- Grounding the randomness of quantum measurement
- Cryptographic hash functions from sequences of lifted Paley graphs
- Pseudorandomness in computer science and in additive combinatorics
- The unified theory of pseudorandomness
- Pseudo-randomness: objects and generation
- On the error-correcting radius of folded Reed-Solomon code designs
- A primer on pseudorandom generators
- Pseudorandomness
- Pseudorandom Generators and Typically-Correct Derandomization
- scientific article; zbMATH DE number 1833398 (Why is no real title available?)
- Continuous monitoring of _p norms in data streams
- Optimal deterministic extractors for generalized Santha-Vazirani sources
- Improved list-decodability of random linear binary codes
- Almost tight security in lattices with polynomial moduli -- PRF, IBE, all-but-many LTF, and more
- Organisational hierarchy constructions with easy Kuramoto synchronisation
- Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes
- Typically-correct derandomization for small time and space
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- scientific article; zbMATH DE number 7561748 (Why is no real title available?)
- scientific article; zbMATH DE number 7561753 (Why is no real title available?)
- List Decoding and Pseudorandom Constructions
- Pseudorandomness and Combinatorial Constructions
- Randomness in post-selected events
- Rank-metric codes and their applications
- A construction of combinatorial NLTS
- Quasirandomness in hypergraphs
- Fragile complexity of adaptive algorithms
- Superfast coloring in CONGEST via efficient color sampling
- Fragile complexity of adaptive algorithms
- Pseudorandom generators without the XOR lemma
- Fully adaptive decentralized multi-authority \textsf{ABE}
- scientific article; zbMATH DE number 7758305 (Why is no real title available?)
- Component stability in low-space massively parallel computation
- Indistinguishable predictions and multi-group fair learning
- Paradigms for Unconditional Pseudorandom Generators
- Derandomizing Knockoffs
- Nonmalleable digital lockers and robust fuzzy extractors in the plain model
- Secure Sketch and Fuzzy Extractor with Imperfect Randomness: An Information-Theoretic Study
- Estimates of the Number of Edges in Subgraphs of Johnson Graphs
- Leakage-resilient \textsf{IBE}/\textsf{ABE} with optimal leakage rates from lattices
- Strong blocking sets and minimal codes from expander graphs
- Near-optimal distributed computation of small vertex cuts
- Multi-instance randomness extraction and security against bounded-storage mass surveillance
- One-tape Turing machine and branching program lower bounds for MCSP
- Decoupling by local random unitaries without simultaneous smoothing, and applications to multi-user quantum information tasks
- Pseudorandom generators for sliding-window algorithms
- Seed-protecting extractors
- Iterated decomposition of biased permutations via new bounds on the spectral gap of Markov chains
- The computational advantage of MIP* vanishes in the presence of noise
- Pseudorandomness, symmetry, smoothing: I
- Derandomization with pseudorandomness
- Testing spreading behavior in networks with arbitrary topologies
- Positivity of Schubert coefficients
- Expanders and growth of normal subsets in finite simple groups of Lie type
- Pseudorandom linear codes are list-decodable to capacity
- Total NP search problems with abundant solutions
- Extractors for polynomial sources over \(\mathbb{F}_2\)
- Explicit and near-optimal construction of t-rankwise independent permutations
- Towards simpler sorting networks and monotone circuits for majority
- Optimal pseudorandom generators for low-degree polynomials over moderately large fields
- Worst-case to average-case hardness of LWE: an alternative perspective
- Distributing keys and random secrets with constant complexity
- Leakage-resilient incompressible cryptography: constructions and barriers
- Almost tight security in lattices with polynomial moduli -- PRF, IBE, all-but-many LTF, and more
- Sharp threshold rates for random codes
- Leakage-resilient hardness equivalence to logspace derandomization
- Undefinability of approximation of 2-to-2 games
- Some exact and asymptotic results for hypergraph Turán problems in _2-norm
- Multi-source randomness extraction and generation in the random-oracle model
- Pseudodistributions that beat all pseudorandom generators
- Efficient quantum pseudorandomness from Hamiltonian phase states
- Modular aggregation as a debiasing method for non-stationary discrete sources: convergence and numerical validation
- Fault-tolerant labeling and compact routing schemes
- Low-degree polynomials are good extractors
- Pseudorandomness of expander walks via Fourier analysis on groups
- On sums of INW pseudorandom generators
- Expander Graphs
- Derandomization with Conditional Expectations
- Model independent approach to probabilistic models
- Robustly reusable fuzzy extractor with imperfect randomness
This page was built for publication: Pseudorandomness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2869768)
