  In a breakthrough work, Marcus-Spielman-Srivastava recently showed that every
$d$-regular bipartite Ramanujan graph has a 2-lift that is also $d$-regular
bipartite Ramanujan. As a consequence, a straightforward iterative brute-force
search algorithm leads to the construction of a $d$-regular bipartite Ramanujan
graph on $N$ vertices in time $2^{O(dN)}$. Shift $k$-lifts studied by
Agarwal-Kolla-Madan lead to a natural approach for constructing Ramanujan
graphs more efficiently. The number of possible shift $k$-lifts of a
$d$-regular $n$-vertex graph is $k^{nd/2}$. Suppose the following holds for
$k=2^{\Omega(n)}$:
  There exists a shift $k$-lift that maintains the Ramanujan property of
$d$-regular bipartite graphs on $n$ vertices for all $n$. (*)
  Then, by performing a similar brute-force search algorithm, one would be able
to construct an $N$-vertex bipartite Ramanujan graph in time $2^{O(d\,log^2
N)}$. Furthermore, if (*) holds for all $k \geq 2$, then one would obtain an
algorithm that runs in $\mathrm{poly}_d(N)$ time. In this work, we take a first
step towards proving (*) by showing the existence of shift $k$-lifts that
preserve the Ramanujan property in $d$-regular bipartite graphs for $k=3,4$.
