This introduction to the theory of pseudorandomness offers a fresh perspective on the concept of randomness, rooted in a complexity-theoretic approach. At its core, this approach posits that a distribution is considered random (or pseudorandom) if no efficient procedure can distinguish it from the uniform distribution. Consequently, randomness becomes a subjective quality dependent on the observer, rather than an inherent property of an object.
In its extreme form, this approach dismisses the relevance of whether the world is inherently deterministic or allows for free choice. Instead, the focus is on how the world appears to us and to various computationally bounded devices. If a phenomenon appears random, it may be treated as such. Similarly, if sequences can be generated indistinguishably from the uniform distribution by efficient procedures, they can be employed in any efficient randomized application in lieu of ideal coin tosses envisioned in the application’s design.
Central to this approach is the concept of computational indistinguishability, referring to pairs of distributions that defy differentiation by efficient procedures. While the primary embodiment involves efficient procedures associated with polynomial-time algorithms, other versions that consider diverse classes of distinguishing procedures yield valuable insights. The practical generation of pseudorandom objects, a significant concern, represents a versatile paradigm with varied incarnations dictated by different computational complexity constraints imposed on the generation process.
Aligned with these principles, we provide a concise overview of key elements in the theory of pseudorandomness. The pivotal concept is the pseudorandom generator, an efficient deterministic procedure that elongates short random seeds into extended pseudorandom sequences. Consequently, a generic formulation of pseudorandom generators involves specifying three critical aspects: the stretch measure of generators and the class of distinguishers they accommodate.
Download
See also
- Software Exorcism: A Handbook for Debugging and Optimizing Legacy Code by Bill Blunden (2003)
- Hormones and the Endocrine System: Textbook of Endocrinology by Bernhard Kleine (2016)
- Genetics: A Conceptual Approach 6e by Benjamin A. Pierce (2017)
- A Functional Approach to Java by Ben Weidig (2022)
- Calculus of variations and optimal control by Amol Sasan (2005)