TR11-081 Authors: Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar

Publication: 16th May 2011 14:19

Downloads: 3126

Keywords:

Given a finite group $G$ by its multiplication table as input, we give a deterministic polynomial-time construction of a directed Cayley graph on $G$ with $O(\log |G|)$ generators, which has a rapid mixing property and a constant spectral expansion.\\

We prove a similar result in the undirected case, and give a new deterministic polynomial-time construction of an expanding Cayley graph with $O(\log |G|)$ generators, for any group $G$ given by its multiplication table. This gives a completely different and

elementary proof of a result of Wigderson and Xiao.\\

For any finite group $G$ given by a multiplication table, we give a deterministic polynomial-time construction of a cube generating

sequence that gives a distribution on $G$ which is arbitrarily close to the uniform distribution. This derandomizes the construction of Erdos-Renyi sequences.