{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:42:56Z","timestamp":1787323376586,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"UMI-Relax"},{"name":"UMI-Relax"},{"DOI":"10.13039\/501100007296","name":"Infosys Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007296","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007296","name":"Infosys Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007296","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Let $G =\\langle S\\rangle$ be a solvable permutation group given as input by the generating set $S$, that is, $G$ is a solvable subgroup of the symmetric group $S_n$. We give a deterministic polynomial-time algorithm that computes an expanding generating set $T$ of size $\\tilde{O}(n^2(1\/\\lambda)^{c})$ for $G$ such that the undirected Cayley graph ${\\rm Cay}_u(G,T)$ is a $\\lambda$-spectral expander and the constant $c$ is at most $8$ (the $\\tilde{O}$ notation suppresses $\\log ^{O(1)}n$ and $\\log ^{O(1)}(1\/\\lambda)$ factors). As a byproduct of our proof, we get a new explicit construction of $\\varepsilon$-bias spaces of size $\\tilde{O}(n (\\log d)^{O(1)}(1\/\\varepsilon)^{c})$ for the groups $\\mathbb{Z}_d^n$ and $c\\leq 8$. The earlier known size bound was $O((d + n\/\\varepsilon^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\\le S_n$ given by a generating set, in deterministic polynomial time we can compute an expanding generating set $T$ of size $\\left({n}\/{\\lambda}\\right)^{O(1)}$ such that ${\\rm Cay}_u(G,T)$ is a $\\lambda$-spectral expander where the $O(1)$ notation involves a large constant.<\/jats:p>","DOI":"10.1137\/17m1148979","type":"journal-article","created":{"date-parts":[[2018,7,19]],"date-time":"2018-07-19T14:21:49Z","timestamp":1532010109000},"page":"1721-1740","source":"Crossref","is-referenced-by-count":0,"title":["Expanding Generating Sets for Solvable Permutation Groups"],"prefix":"10.1137","volume":"32","author":[{"given":"V.","family":"Arvind","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Partha","family":"Mukhopadhyay","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prajakta","family":"Nimbhorkar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yadu","family":"Vasudev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,7,19]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/18.119713"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/22.6.583"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009813"},{"key":"atypb5","first-page":"37","author":"Arvind V.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050203"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103440"},{"key":"atypb8","first-page":"229","author":"Babai L.","year":"1984","journal-title":"Singer Island, FL"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"S. Chen, C. Moore, and A. Russell,\n                      Small-bias sets for non-Abelian groups - derandomizations of the Alon-Roichman theorem\n                      , in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX 2013, RANDOM 2013, Lecture Notes in Comput. Sci. 8096. Springer, Berlin, Heidelberg, pp. 436-451.","DOI":"10.1007\/978-3-642-40328-6_31"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01111027"},{"key":"atypb11","first-page":"439","volume":"43","author":"Hoory S.","year":"2006","journal-title":"S.)"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90038-6"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"atypb14","first-page":"139","author":"Luks E. M.","year":"1993","journal-title":"RI"},{"key":"atypb15","first-page":"95","author":"Lubotzky A.","year":"1993","journal-title":"RI"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"atypb17","first-page":"436","author":"Rozenman E.","year":"2005","journal-title":"Berlin"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"O. Reingold, S. P. Vadhan, and A. Wigderson,\n                      Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors\n                      , in Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000, pp. 3-13.","DOI":"10.1109\/SFCS.2000.892006"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"A\u0301. Seress,\n                      Permutation Group Algorithms\n                      , Cambridge Tracts in Math. 152, Cambridge University Press, Cambridge, 2003.","DOI":"10.1017\/CBO9780511546549"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"A. Ta-Shma,\n                      Explicit, almost optimal, epsilon-balanced codes\n                      , in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, Montreal, Quebec, ACM, New York, 2017, pp. 238-251.","DOI":"10.1145\/3055399.3055408"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a003"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1148979","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:58:38Z","timestamp":1787320718000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1148979"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1148979"],"URL":"https:\/\/doi.org\/10.1137\/17m1148979","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}