Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-081 | 15th May 2011 08:54

Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs

RSS-Feed




TR11-081
Authors: Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar
Publication: 16th May 2011 14:19
Downloads: 4518
Keywords: 


Abstract:

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