Computing a shortest path from a source s to a destination t in an undirected unweighted graph is a basic algorithmic problem with the classic Breadth First Search (BFS) algorithm solving it optimally in linear time. But is it possible to solve the problem in sublinear time? That is, without even looking at the entire graph. It is not hard to show that this is impossible in general. A common practical heuristic used to speed up BFS is to run it simultaneously from both the source and destination. While having no asymptotic benefits in the worst case, this has been shown to improve the running time to around the square-root of the number of vertices in the graph when the input graph is chosen randomly, e.g. as an Erdös-Rényi random graph.
In this work, which was presented at the MFCS'24 (Mathematical Foundations of Computer Science) conference, we identify a natural "deterministic" property of a graph that also implies sublinear time shortest paths from bidirectional BFS. This property is the well-studied notion of being a (spectral) expander graph. The video introduces all these concepts and gives a proof of sublinear time in expanders.