  We present a new technique for efficiently removing almost all short cycles
in a graph without unintentionally removing its triangles. Consequently,
triangle finding problems do not become easy even in almost $k$-cycle free
graphs, for any constant $k\geq 4$.
  Triangle finding is at the base of many conditional lower bounds in P, mainly
for distance computation problems, and the existence of many $4$- or $5$-cycles
in a worst-case instance had been the obstacle towards resolving major open
questions.
  Hardness of approximation: Are there distance oracles with $m^{1+o(1)}$
preprocessing time and $m^{o(1)}$ query time that achieve a constant
approximation? Existing algorithms with such desirable time bounds only achieve
super-constant approximation factors, while only $3-\epsilon$ factors were
conditionally ruled out (P\u{a}tra\c{s}cu, Roditty, and Thorup; FOCS 2012). We
prove that no $O(1)$ approximations are possible, assuming the $3$-SUM or APSP
conjectures. In particular, we prove that $k$-approximations require
$\Omega(m^{1+1/ck})$ time, which is tight up to the constant $c$. The lower
bound holds even for the offline version where we are given the queries in
advance, and extends to other problems such as dynamic shortest paths.
  The $4$-Cycle problem: An infamous open question in fine-grained complexity
is to establish any surprising consequences from a subquadratic or even
linear-time algorithm for detecting a $4$-cycle in a graph. We prove that
$\Omega(m^{1.1194})$ time is needed for $k$-cycle detection for all $k\geq 4$,
unless we can detect a triangle in $\sqrt{n}$-degree graphs in
$O(n^{2-\delta})$ time; a breakthrough that is not known to follow even from
optimal matrix multiplication algorithms.
