  Among the most important graph parameters is the Diameter, the largest
distance between any two vertices. There are no known very efficient algorithms
for computing the Diameter exactly. Thus, much research has been devoted to how
fast this parameter can be approximated. Chechik et al. showed that the
diameter can be approximated within a multiplicative factor of $3/2$ in
$\tilde{O}(m^{3/2})$ time. Furthermore, Roditty and Vassilevska W. showed that
unless the Strong Exponential Time Hypothesis (SETH) fails, no
$O(n^{2-\epsilon})$ time algorithm can achieve an approximation factor better
than $3/2$ in sparse graphs. Thus the above algorithm is essentially optimal
for sparse graphs for approximation factors less than $3/2$. It was, however,
completely plausible that a $3/2$-approximation is possible in linear time. In
this work we conditionally rule out such a possibility by showing that unless
SETH fails no $O(m^{3/2-\epsilon})$ time algorithm can achieve an approximation
factor better than $5/3$.
  Another fundamental set of graph parameters are the Eccentricities. The
Eccentricity of a vertex $v$ is the distance between $v$ and the farthest
vertex from $v$. Chechik et al. showed that the Eccentricities of all vertices
can be approximated within a factor of $5/3$ in $\tilde{O}(m^{3/2})$ time and
Abboud et al. showed that no $O(n^{2-\epsilon})$ algorithm can achieve better
than $5/3$ approximation in sparse graphs. We show that the runtime of the
$5/3$ approximation algorithm is also optimal under SETH. We also show that no
near-linear time algorithm can achieve a better than $2$ approximation for the
Eccentricities and that this is essentially tight: we give an algorithm that
approximates Eccentricities within a $2+\delta$ factor in $\tilde{O}(m/\delta)$
time for any $0<\delta<1$. This beats all Eccentricity algorithms in Cairo et
al.
