Options
Vasudev Yadu
Loading...
Preferred name
Vasudev Yadu
Official Name
Vasudev Yadu
Alternative Name
Vasudev, Y.
Vasudev, Yadu
Main Affiliation
Email
ORCID
Scopus Author ID
Google Scholar ID
1 results
Now showing 1 - 1 of 1
- PublicationExpanding generating sets for solvable permutation groups(01-01-2018)
;Arvind, V. ;Mukhopadhyay, Partha ;Nimbhorkar, PrajaktaLet G = S be a solvable permutation group given as input by the generating set S, that is, G is a solvable subgroup of the symmetric group Sn. We give a deterministic polynomial-time algorithm that computes an expanding generating set T of size O(n2(1/λ)c) for G such that the undirected Cayley graph Cayu(G, T) is a λ-spectral expander and the constant c is at most 8 (the O notation suppresses logO(1) n and logO(1)(1/λ) factors). As a byproduct of our proof, we get a new explicit construction of ε-bias spaces of size O(n(log d)O(1)(1/ε)c) for the groups Znd and c ≤ 8. The earlier known size bound was O((d + n/ε2)11/2) given by [Y. Azar, R. Motwani, and J. Naor, Combinatorica, 18 (1998), pp. 151-171]. We also note that for any permutation group G ≤ Sn given by a generating set, in deterministic polynomial time we can compute an expanding generating set T of size (n/λ)O(1) such that Cayu(G, T) is a λ-spectral expander where the O(1) notation involves a large constant.