ECCC-Report TR11-081https://eccc.weizmann.ac.il/report/2011/081Comments and Revisions published for TR11-081en-usMon, 16 May 2011 14:19:38 +0300
Paper TR11-081
| Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs |
Vikraman Arvind,
Partha Mukhopadhyay,
Prajakta Nimbhorkar
https://eccc.weizmann.ac.il/report/2011/081Given 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.Mon, 16 May 2011 14:19:38 +0300https://eccc.weizmann.ac.il/report/2011/081