Generating Expander Graphs Using Cellular Automata

摘要

The paper characterizes a special class of Cellular Automaton (CA) called Two Predecessor Single Attractor CA (TPSA-CA). We show that the transition graphs of the TPSA-CA can be used to realize pseudo-random regular graphs with good expansion properties. The elegance of the scheme lies in the fact that the storage required to capture the graph is O(logN), where N is the total number of vertices in the graph.