Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-140 | 25th November 2011 14:36

Expanding Generator Sets for Solvable Permutation Groups

RSS-Feed




Revision #1
Authors: Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev
Accepted on: 25th November 2011 14:36
Downloads: 1424
Keywords: 


Abstract:

Let $G=\langle S\rangle$ be a solvable permutation group given as input by generating set $S$. I.e.\ $G$ is a solvable subgroup of the symmetric group $S_n$. We give a deterministic polynomial-time algorithm that computes an expanding generator set for $G$. More precisely, given a constant $\lambda <1$ we can compute an expanding generator set $T$ of size $n^2(\log n)^{O(1)}$ such that the undirected Cayley graph Cay$(G,T)$ is a $\lambda$-spectral expander. In particular, this construction yields $\epsilon$-bias spaces with improved size bounds for the groups $\mathbb{Z}_d^n$ for any constant bias $\epsilon$.



Changes to previous version:

A new subsection (Section 2.2) about general permutation groups is included.


Paper:

TR11-140 | 31st October 2011 15:09

Expanding Generator Sets for Solvable Permutation Groups





TR11-140
Authors: Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev
Publication: 31st October 2011 16:01
Downloads: 1939
Keywords: 


Abstract:

Let $G=\langle S\rangle$ be a solvable permutation group given as input by generating set $S$. I.e.\ $G$ is a solvable subgroup of the symmetric group $S_n$. We give a deterministic polynomial-time algorithm that computes an expanding generator set for $G$. More precisely, given a constant $\lambda <1$ we can compute an expanding generator set $T$ of size $n^2(\log n)^{O(1)}$ such that the undirected Cayley graph Cay$(G,T)$ is a $\lambda$-spectral expander. In particular, this construction yields $\epsilon$-bias spaces with improved size bounds for the groups $\mathbb{Z}_d^n$ for any constant bias $\epsilon$.



ISSN 1433-8092 | Imprint