We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map π : H → G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n "new" eigenvalues. We conjecture that every d-regular graph has a 2-lift such that all new eigenvalues are in the range \left[ { - 2\sqrt {d - 1} ,2\sqrt {d - 1} } \right] (If true, this is tight, e.g. by the Alon-Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all "new" eigenvalues are in the range \left[ { - c\sqrt {d\log ^3 d} ,c\sqrt {d\log ^3 d} } \right] for some constant c. This leads to a polynomial time algorithm for constructing arbitrarily large d-regular graphs, with second eigenvalue 0(\sqrt {d\log ^3 d}).

The proof uses the following lemma (Lemma 3.6): Let A be a real symmetric matrix with zeros on the diagonal. Let d be such that the ι₁ norm of each row in A is at most d. Suppose that \frac{{\left| {xAy} \right|}}{{\left\| x \right\|\left\| y \right\|}} \leqslant \alpha for every x,y \in \{ 0,1\} ^n with 〈 x,y 〉 = 0. Then the spectral radius of A is 0(\alpha (\log ({d \mathord{\left/ {\vphantom {d {\alpha ) + 1))}}} \right. \kern-\nulldelimiterspace} {\alpha ) + 1))}}. An interesting consequence of this lemma is a converse to the Expander Mixing Lemma.