An optimal algorithm for average distance in typical regular graphs

We design a deterministic algorithm that, given $n$ points in a \emph{typical} constant degree regular~graph, queries $O(n)$ distances to output a constant factor approximation to the average distance among those points, thus answering a question posed in~\cite{MN14}. Our algorithm uses the method of~\cite{MN14} to construct a sequence of constant degree graphs that are expanders with respect to certain nonpositively curved metric spaces, together with a new rigidity theorem for metric transforms of nonpositively curved metric spaces. The fact that our algorithm works for typical (uniformly random) constant degree regular graphs rather than for all constant degree graphs is unavoidable, thanks to the following impossibility result that we obtain: For every fixed $k\in \N$, the approximation factor of any algorithm for average distance that works for all constant degree graphs and queries $o(n^{1+1/k})$ distances must necessarily be at least $2(k+1)$. This matches the upper bound attained by the algorithm that was designed for general finite metric spaces in~\cite{BGS}. Thus, any algorithm for average distance in constant degree graphs whose approximation guarantee is less than $4$ must query $Ω(n^2)$ distances, any such algorithm whose approximation guarantee is less than $6$ must query $Ω(n^{3/2})$ distances, any such algorithm whose approximation guarantee less than $8$ must query $Ω(n^{4/3})$ distances, and so forth, and furthermore there exist algorithms achieving those parameters.