  There has been significant recent progress on algorithms for approximating
graph spanners, i.e., algorithms which approximate the best spanner for a given
input graph. Essentially all of these algorithms use the same basic LP
relaxation, so a variety of papers have studied the limitations of this
approach and proved integrality gaps for this LP in a variety of settings. We
extend these results by showing that even the strongest lift-and-project
methods cannot help significantly, by proving polynomial integrality gaps even
for $n^{\Omega(\epsilon)}$ levels of the Lasserre hierarchy, for both the
directed and undirected spanner problems. We also extend these integrality gaps
to related problems, notably Directed Steiner Network and Shallow-Light Steiner
Network.
