Near-optimal expanding generator sets for solvable permutation groups

Publication date 25 September 2012

Abstract: Let

G = < S >

be a solvable permutation group of the symmetric group

S_{n}

given as input by the generating set

S

. We give a deterministic polynomial-time algorithm that computes an emph{expanding generating set} of size

i l d e O (n^{2})

for

G

. More precisely, the algorithm computes a subset

T s u b s e t G

of size

i l d e O (n^{2}) (1 / l a m b d a)^{O (1)}

such that the undirected Cayley graph

C a y (G, T)

is a

l a m b d a

-spectral expander (the

i l d e O

notation suppresses

l o g^{O (1)} n

factors). As a byproduct of our proof, we get a new explicit construction of

v a r e p s i l o n

-bias spaces of size

i l d e O (n p o l y (l o g d)) (f r a c 1 v a r e p s i l o n)^{O (1)}

for the groups

. The earlier known size bound was

O ((d + n / v a r e p s i l o n^{2}))^{11 / 2}

given by cite{AMN98}.

Recommendations

Cited in

(3)

This page was built for publication: Near-optimal expanding generator sets for solvable permutation groups