Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-081 | 15th May 2011 08:54

Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs


Authors: Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar
Publication: 16th May 2011 14:19
Downloads: 2102


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.

ISSN 1433-8092 | Imprint