Near-Optimal Expanding Generating Sets for Solvable Permutation Groups
summary
Constructs explicit expanding generating sets for solvable subgroups of S_n by using the group’s derived series to reduce to abelian quotients, lifting expanders across onto homomorphisms, and improving spectral gaps by derandomized squaring. The algorithm produces lambda‑expanders whose size is almost logarithmic in the abelian modulus factors (using known expanders for Z_T), so the overall size stays close to the randomized bound; for arbitrary permutation groups the method only yields much larger n^{O(1)} sets.
AI-written summary · about
chapters (12)
- 0:00Intro
- 1:11Expander Graphs
- 2:37Cayley graphs
- 4:43Cayley Expanders
- 5:06Do all groups have expanding generating sets?
- 7:43Combining generating sets
- 9:28Expanding Generating Set for G
- 10:25Constructing expanding generating sets for G
- 10:35Abelian quotient groups
- 11:37Bootstrapping step
- 12:41Bootstrapping, again
- 14:24Conclusion
related talks
20mCounting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
58mExponential-Time Algorithms
31mFaster Satisfiability Algorithms for Systems of Polynomial Equations over Finite Fields and ACC^0[p]
27mList Recovery and Local Decoding of Expander Codes
55mSparsification Lemma and ETH
17mSatisfiability Algorithms Based on Concentrated Shrinkage
56mSatisfiability Algorithms II
23mTowards General and Tight Hardness Results for Graph Problems