Many previous works derive consequences from high-girth graphs for distance computation problems.
For example, in lower bounds for graph sparsification (spanners) [1]}, [2]} or compression (distance oracles) [3]}, [4]}, [5]}, [6]}, and for the number of rounds in a distributed setting [7]}, [8]} the lower bound constructions are built on constructions of a high-girth graph, either explicit (see [9]}) or hypothetical under the Girth Conjecture [10]}.
Unfortunately, no one has managed to make such an approach work for conditional lower bounds in P, because such constructions are too structured to be worst-case graphs and cannot encode a hard worst-case instance of another problem such as 3SUM.
Our approach is diametrically opposed: we start from a worst-case graph and efficiently turn it into an (almost) high-girth graph by our short cycle removal technique (albeit with worse parameters than the best explicit constructions).
