Theory Seminar, Wednesday Dec 24: Manor Mendel (OpenU) - An optimal algorithm for average distance in typical regular graphs

[Arnold Filtser]

Hi all,

Next week (Wed Dec 24, at 12) we will meet for our theory seminar.

Location: Building 503 room 226.

Looking forward to seeing you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Manor Mendel (Open University of Israel)
Title: An optimal algorithm for average distance in typical regular graphs
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 [Mendel and Naor 2015].
Our algorithm uses the method of [Mendel and Naor 2015] 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 \mathbb 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 an algorithm that was designed for general finite metric spaces by [Barhum, Goldreich, and Shraibman, 2007].

Based on a joint work with Alexandros Eskenazis and Assaf Naor (SODA 2026 and https://arxiv.org/abs/2510.18722).

[Arnold Filtser]

The talk starts in one hour!