  We consider the $0$-Extension problem, where we are given an undirected graph
$\mathcal{G}=(V,E)$ equipped with non-negative edge weights $w:E\rightarrow
\mathbb{R}^+$, a collection $ T=\{ t_1,\ldots,t_k\}\subseteq V$ of $k$ special
vertices called terminals, and a semi-metric $D$ over $T$. The goal is to
assign every non-terminal vertex to a terminal while minimizing the sum over
all edges of the weight of the edge multiplied by the distance in $D$ between
the terminals to which the endpoints of the edge are assigned. $0$-Extension
admits two known algorithms, achieving approximations of $O(\log{k})$
[C{\u{a}}linescu-Karloff-Rabani SICOMP '05] and $O(\log{k}/\log{\log{k}})$
[Fakcharoenphol-Harrelson-Rao-Talwar SODA '03]. Both known algorithms are based
on rounding a natural linear programming relaxation called the metric
relaxation, in which $D$ is extended from $T$ to the entire of $V$. The current
best known integrality gap for the metric relaxation is $\Omega
(\sqrt{\log{k}})$. In this work we present an improved integrality gap of
$\Omega(\log^{\frac{2}{3}}k)$ for the metric relaxation. Our construction is
based on the randomized extension of one graph by another, a notion that
captures lifts of graphs as a special case and might be of independent
interest. Inspired by algebraic topology, our analysis of the gap instance is
based on proving no continuous section (in the topological sense) exists in the
randomized extension.
