Simple Permutations Mix Even Better
| dc.creator | Hoory, Shlomo | |
| dc.creator | Brodsky, Alex | |
| dc.date | 2004-11-04 | |
| dc.date | 2005-06-08 | |
| dc.date.accessioned | 2026-07-07T05:13:59Z | |
| dc.date.available | 2026-07-07T05:13:59Z | |
| dc.description | We study the random composition of a small family of O(n^3) simple permutations on {0,1}^n. Specifically we ask how many randomly selected simple permutations need be composed to yield a permutation that is close to k-wise independent. We improve on the results of Gowers 1996 and Hoory, Magen, Myers and Rackoff 2004, and show that up to a polylogarithmic factor, n^2*k^2 compositions of random permutations from this family suffice. In addition, our results give an explicit construction of a degree O(n^3) Cayley graph of the alternating group of 2^n objects with a spectral gap Omega(2^{-n}/n^2), which is a substantial improvement over previous constructions. | |
| dc.description | Better statement and proof of Theorem 9 | |
| dc.identifier | https://arxiv.org/abs/math/0411098 | |
| dc.identifier | http://arxiv.org/abs/math/0411098 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/73110 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C50;05C25;60J10 | |
| dc.title | Simple Permutations Mix Even Better | |
| dc.type | text |