Pseudorandomness

Pseudorandomness is the study of deterministic processes that generate outputs indistinguishable from true randomness by computationally bounded observers. In computational complexity, a pseudorandom generator stretches a short random seed into a long sequence that fools polynomial-time algorithms. Expander graphs play a central role: random walks on expanders generate pseudorandom bits with minimal true randomness, bridging deterministic structure and stochastic behavior. Pseudorandomness reveals that randomness is not a property of objects but of relationships — specifically, of the relationship between a generator and the class of observers it fools.

The philosophical force of pseudorandomness is often missed by treating it as a technical tool for derandomization. It is better understood as a claim about the nature of randomness itself: that randomness is observer-dependent, that what looks random to a bounded mind may be completely determined to a more powerful one, and that the boundary between order and chaos is not a property of the world but a property of the observer's computational limits.

Pseudorandomness Across Domains

The concept of pseudorandomness is not limited to computational complexity. In cryptography, the security of stream ciphers depends on pseudorandom generators whose outputs are indistinguishable from random by any efficient adversary — a strictly stronger requirement than the complexity-theoretic one, which only demands indistinguishability by specific algorithm classes. The Blum-Blum-Shub generator, based on the hardness of quadratic residuosity, is provably pseudorandom under cryptographic assumptions, bridging number theory and security proofs.

In statistical mechanics, pseudorandomness appears in the form of pseudorandom spin configurations and the study of deterministic dynamical systems that exhibit statistical regularities indistinguishable from thermal ensembles. The ergodic hypothesis — that time averages equal ensemble averages for almost all initial conditions — is, in effect, a claim about pseudorandomness in physical systems: the deterministic evolution of a system can fool an observer who measures only coarse-grained properties.

In quantum mechanics, the question of pseudorandomness takes a stranger form. Quantum randomness is often claimed to be 'true' randomness, certified by Bell inequality violations. But this claim assumes that the quantum state is not governed by hidden deterministic dynamics. From the perspective of pseudorandomness, quantum randomness might simply be deterministic evolution that fools all physically realizable measurements — a pseudorandom generator whose seed is the initial quantum state and whose observer class is bounded by the no-signaling principle.

The cross-domain pattern is unmistakable: pseudorandomness is the generic phenomenon that arises whenever a deterministic system is observed through a restricted window. The restriction might be computational complexity, coarse-grained measurement, or relativistic causality. In each case, the observer's limitations create the appearance of randomness, and the study of those limitations reveals the structure of the underlying system. Randomness is not a resource to be harvested; it is a shadow cast by the boundary between what a system is and what an observer can see.