How much geometry can be recovered from a random graph? Consider points sampled from an unknown space, with edges drawn independently according to a function of the distance between their endpoints. I will discuss a sequence of results on efficient reconstruction when the underlying space is a manifold, including results for sparse graphs and for unknown connection functions. I will also explain what makes manifold geometry special and illustrate the information-theoretic obstructions that arise in more general metric spaces.
Based on joint work with Pakawut Jiradilok and Elchanan Mossel.