Title: An optimal algorithm for average distance in typical regular graphs Show Chinese title

Title: 典型正则图中平均距离的最优算法

Abstract: 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 $\Omega(n^2)$ distances, any such algorithm whose approximation guarantee is less than $6$ must query $\Omega(n^{3/2})$ distances, any such algorithm whose approximation guarantee less than $8$ must query $\Omega(n^{4/3})$ distances, and so forth, and furthermore there exist algorithms achieving those parameters. Show Chinese abstract

Abstract: 我们设计了一个确定性算法，给定$n$个点在一个\emph{典型的}常数度正则图中，查询$O(n)$个距离以输出这些点之间平均距离的常数因子近似值，从而回答了~\cite{MN14}提出的问题。 我们的算法使用~\cite{MN14}的方法构造一系列相对于某些非正曲率度量空间是扩张器的常数度图，以及一个关于非正曲率度量空间的度量变换的新刚性定理。 我们的算法适用于典型的（均匀随机）常度正则图，而不是所有常度图，这是不可避免的，这归功于我们得到的以下不可能性结果：对于每个固定的$k\in \N$，对于所有常度图且查询$o(n^{1+1/k})$个距离的平均距离问题的任何算法的近似因子必须至少为$2(k+1)$。这与在~\cite{BGS}中为一般有限度量空间设计的算法所达到的上界相匹配。 因此，任何用于常度图平均距离的算法，如果其近似保证小于$4$，则必须查询$\Omega(n^2)$个距离，任何此类算法如果其近似保证小于$6$，则必须查询$\Omega(n^{3/2})$个距离，任何此类算法如果其近似保证小于$8$，则必须查询$\Omega(n^{4/3})$个距离，依此类推，而且存在达到这些参数的算法。