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.