Fall 2016

Near-Optimal Expanding Generating Sets for Solvable Permutation Groups

Thursday, November 10th, 2016 3:00 pm3:30 pm

Add to Calendar

Let G be a solvable subgroup of the symmetric group S_n given as input by the generating set S. We give a deterministic polynomial time algorithm that computes an expanding generating set of size \tilde{O}(n^2) for G.