  We prove that the permanent of nonnegative matrices can be deterministically
approximated within a factor of $\sqrt{2}^n$ in polynomial time, improving upon
the previous deterministic approximations. We show this by proving that the
Bethe approximation of the permanent, a quantity computable in polynomial time,
is at least as large as the permanent divided by $\sqrt{2}^{n}$. This resolves
a conjecture of Gurvits. Our bound is tight, and when combined with previously
known inequalities lower bounding the permanent, fully resolves the quality of
Bethe approximation for permanent. As an additional corollary of our methods,
we resolve a conjecture of Chertkov and Yedidia, proving that fractional belief
propagation with fractional parameter $\gamma=-1/2$ yields an upper bound on
the permanent.
