  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 $\pi:H \to 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 $[-2\sqrt{d-1},2\sqrt{d-1}]$ (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 $[-c \sqrt{d \log^3d}, c \sqrt{d \log^3d}]$ for some constant $c$.
This leads to a polynomial time algorithm for constructing arbitrarily large
$d$-regular graphs, with second eigenvalue $O(\sqrt{d \log^3 d})$.
  The proof uses the following lemma: Let $A$ be a real symmetric matrix such
that the $l_1$ norm of each row in $A$ is at most $d$. Let $\alpha = \max_{x,y
\in \{0,1\}^n, supp(x)\cap supp(y)=\emptyset} \frac {|xAy|} {||x||||y||}$. Then
the spectral radius of $A$ is at most $c \alpha \log(d/\alpha)$, for some
universal constant $c$.
  An interesting consequence of this lemma is a converse to the Expander Mixing
Lemma.
