TR-96-05: Boolean Routing on Cayley Networks

We study Boolean routing on Cayley networks. Let K(M_G) denote the Kolmogorov complexity of the multiplication table of a group G of order n. We show that O(max { d log n, K(M_G) } ) memory bits per local router (hence a total of O(n max { d log n, K(M_G) } )$ memory bits) are sufficient to do Boolean routing on the Cayley network constructed from the group G and a set of d generators. It is a consequence of the classification theorem for finite simple groups that K(M_G) in O(log^3 n). Even better complexity bounds are known for classes of groups. E.g., if n is the power of a prime p then K(M_G) in O(log^3 n/ \log^2 p); if n is square-free or G is abelian then K(M_G) in O(log n). A lower bound $Omega (n d log d + n log n ) on the total number of memory bits is given in cite{flammini}.