A Note on Hardness of Diameter Approximation

We revisit the hardness of approximating the diameter of a network. In the CONGEST model of distributed computing, $\tilde{\mathrm{\Omega }}(n)$ rounds are necessary to compute the diameter [Frischknecht et al. SODA’12], where $ \tilde \Omega (\cdot) $ hides polylogarithmic factors. Abboud et al. [DISC 2016] extended this result to sparse graphs and, at a more fine-grained level, showed that, for any integer $1\le \mathrm{\ell }\le \mathrm{polylog}(n)$, distinguishing between networks of diameter $4\mathrm{\ell }+2$ and $6\mathrm{\ell }+1$ requires $\tilde{\mathrm{\Omega }}(n)$ rounds. We slightly tighten this result by showing that even distinguishing between diameter $2\mathrm{\ell }+1$ and $ 3 \ell + 1 $requires$ \tilde \Omega (n) $ rounds. The reduction of Abboud et al. is inspired by recent conditional lower bounds in the RAM model, where the orthogonal vectors problem plays a pivotal role. In our new lower bound, we make the connection to orthogonal vectors explicit, leading to a conceptually more streamlined exposition.