Pseudorandomness

DOI10.1561/0400000010zbMath1308.68011OpenAlexW4205550388WikidataQ56058888 ScholiaQ56058888MaRDI QIDQ2869768

Salil P. Vadhan

Publication date: 3 January 2014

Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1561/0400000010

zbMATH Keywords

derandomizationcoding theorypseudorandomnessexpander graphrandomness extractor

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Decoding (94B35) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (39)

A construction of combinatorial NLTS ⋮ Almost Tight Security in Lattices with Polynomial Moduli – PRF, IBE, All-but-many LTF, and More ⋮ Constructing locally leakage-resilient linear secret-sharing schemes ⋮ Model independent approach to probabilistic models ⋮ Robustly reusable fuzzy extractor with imperfect randomness ⋮ Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries ⋮ New techniques and tighter bounds for local computation algorithms ⋮ Organisational hierarchy constructions with easy Kuramoto synchronisation ⋮ On the Error-Correcting Radius of Folded Reed–Solomon Code Designs ⋮ Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes ⋮ Fully adaptive decentralized multi-authority \textsf{ABE} ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Grounding the randomness of quantum measurement ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ Component stability in low-space massively parallel computation ⋮ Indistinguishable predictions and multi-group fair learning ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Nonmalleable digital lockers and robust fuzzy extractors in the plain model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Cryptographic hash functions from sequences of lifted Paley graphs ⋮ Unnamed Item ⋮ Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors ⋮ Continuous Monitoring of l_p Norms in Data Streams ⋮ Lossless dimension expanders via linearized polynomials and subspace designs ⋮ Non-malleable coding against bit-wise and split-state tampering ⋮ Quasirandomness in hypergraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Stabilizing network bargaining games by blocking players ⋮ Fragile complexity of adaptive algorithms ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Fragile complexity of adaptive algorithms ⋮ Public-coin statistical zero-knowledge batch verification against malicious verifiers ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Typically-correct derandomization for small time and space ⋮ Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly ⋮ Randomness in post-selected events ⋮ Rank-Metric Codes and Their Applications

This page was built for publication: Pseudorandomness