Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: On Constructing Expanding Generator Sets for Solvable Permutation Groups
event speaker icon
Yadu Vasudev (Chennai Mathematical Institute)
event date icon
Wednesday, 30.04.2014, 12:30
event location icon
Taub 201
The Alon-Roichman theorem states for any finite group $G$ and $\lambda>0$, a multiset $S$ of size $O(\log |G|/\lambda^2)$ picked uniformly at random is a $\lambda$-spectral expander with high probability. Wigderson and Xiao derandomized the Alon-Roichman theorem when the group $G$ is given as a multiplication table. In this talk we study this problem when the group $G$ is a permutation group and is given by a set of generating elements. We will see an algorithm to construct an expanding generating set of size $\tilde{O}(n^2)$ when $G\le S_n$ is a solvable group. We will also see how this algorithm can be used to construct an $\varepsilon$-biased space for $Z_d^n$ of size $O(n(\log(n)\log(d)/\varepsilon)^c)$ for a constant $c$.