ECCC-Report TR11-140https://eccc.weizmann.ac.il/report/2011/140Comments and Revisions published for TR11-140en-usFri, 25 Nov 2011 14:36:24 +0200
Revision 1
| Expanding Generator Sets for Solvable Permutation Groups |
Vikraman Arvind,
Partha Mukhopadhyay,
Prajakta Nimbhorkar,
Yadu Vasudev
https://eccc.weizmann.ac.il/report/2011/140#revision1Let $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$.
Fri, 25 Nov 2011 14:36:24 +0200https://eccc.weizmann.ac.il/report/2011/140#revision1
Paper TR11-140
| Expanding Generator Sets for Solvable Permutation Groups |
Vikraman Arvind,
Partha Mukhopadhyay,
Prajakta Nimbhorkar,
Yadu Vasudev
https://eccc.weizmann.ac.il/report/2011/140Let $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$.
Mon, 31 Oct 2011 16:01:34 +0200https://eccc.weizmann.ac.il/report/2011/140