My free associations led me to an old paper with Avi [see here], where we modify the order of the neighbors in an expander in order to obtain a desired expansion property. This has nothing to do with the current paper; these are merely my free associations.
I find Thm 1.2 more interesting than Thm 1.1, which is sketched in the abstract. It says that sufficiently long walks on any adequately permuted expander converge at a rate that is almost the one of the best expanders of the corresponding degree, even when the original expander has far inferior convergence rate. In other words, the result stated for the Ramanujan case holds for any expander provided that the number of steps (i.e., $t$) is at least $8\lambda^2/d$.
Unfortunately, the existence of a sequence of permutations is shown using the probabilistic method, leave us with the open problem of actually finding such a sequence, when given a base graph (i.e., $G$) and a desired number of steps (i.e., $t$).
Note (4-Dec-22): I just found out that a result similar to Thm 1.2 was proved by Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy, and Avi Wigderson in Almost Ramanujan expanders from arbitrary expanders via operator amplication, Sept 2022. This is mentioned in the current paper (right after Thm 1.2), but I missed it (as well as the posting on arXiv, since I don't follow that depository). In particular, the result of JMRW is strongly explicit; they locally transform any expander into an almost Ramanujan one.
Random walks on expanders are a powerful tool which found applications in many areas of theoretical computer science, and beyond. However, they come with an inherent cost -- the spectral expansion of the corresponding power graph deteriorates at a rate that is exponential in the length of the walk. As an example, when $G$ is a $d$-regular Ramanujan graph, the power graph $G^t$ has spectral expansion $2^{\Omega(t)} \sqrt{D}$, where $D = d^t$ is the regularity of $G^t$, thus, $G^t$ is $2^{\Omega(t)}$ away from being Ramanujan. This exponential blowup manifests itself in many applications.
In this work we bypass this barrier by permuting the vertices of the given graph after each random step. We prove that there exists a sequence of permutations for which the spectral expansion deteriorates by only a linear factor in $t$. In the Ramanujan case this yields an expansion of $O(t \sqrt{D})$. We stress that the permutations are tailor-made to the graph at hand and require no randomness to generate.
Our proof, which holds for all sufficiently high girth graphs, makes heavy use of the powerful framework of finite free probability and interlacing families that was developed in a seminal sequence of works by Marcus, Spielman and Srivastava.
Available from ECCC TR22-163.