Pseudorandom graphs, which have similar connective and spectral properties to random graphs of the same edge density, can be used to reduce the number of bits of randomness used in algorithms. One example of a family of pseudorandom graphs are Paley graphs, the Cayley graph on the integers modulo n under addition generated by quadratic residues modulo n. Cayley graphs have algebraic properties that make them relatively easy to construct, but can give rise to pseudorandom behavior such as that demonstrated by Paley graphs.

Kolmogorov complexity, the length of the shortest possible program specifying an object, can be used to describe the degree of ‘randomness’ exhibited by a single realization of an object. Although not computable, the Kolmogorov complexity of an object can be bounded above using lossless compression algorithms. Thus, proving the Kolmogorov complexity of an object has Kolmogorov complexity lower than that expected of a random string of the same length could be an indicator as to whether that object is helpful for reducing the randomness of an algorithm. We prove that additive Cayley graphs on the integers have sub-random Kolmogorov complexity using the Lempel-Ziv 1976 algorithm. We then briefly discuss the efficacy of Cayley graphs in reducing the randomness used by Echo State Recurrent Neural Networks, which typically rely on a random or random-like graph architecture to effectively forecast chaotic time series data.