Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR11-081 | 15th May 2011 08:54

#### Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs

TR11-081
Authors: Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar
Publication: 16th May 2011 14:19
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