Suppose an unknown point in a metric space can only be accessed via noisy distance measurements to chosen query points. What information about the target can be reconstructed from such data?

---

In this talk we show that, with an unlimited number of queries, what can be reconstructed is exactly determined by a simple geometric invariant: the diameter–radius profile of the underlying metric space. We then ask when this asymptotic benchmark can already be achieved with finitely many queries. We present examples where the limit is attained after finitely many queries (spaces we call “pseudo-finite”) and observe that pseudo-finiteness is a subtle, space-dependent condition. Finally, we contrast this with bounded convex sets in R^d with d > 1, where no finite number of queries ever achieves the limit.

---

All results are from our NeurIPS 2025 paper “Reconstruction and Secrecy under Approximate Distance Queries” (joint with Shay Moran).