# Reconstruction and Secrecy under Approximate Distance Queries

arXiv: https://arxiv.org/abs/2511.06461 · HTML: https://mlsanity.com/paper/2511.06461/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 25 references that are in the map.
- First posted on arXiv 9 Nov 2025.

## Builds on (most cited first, 4 of 4)

- [Reconstructing Training Data with Informed Adversaries](https://mlsanity.com/paper/2201.04845/) (2022)
- [Data Reconstruction: When You See It and When You Don't](https://mlsanity.com/paper/2405.15753/) (2024)
- [On the Complexity of Two-Party Differential Privacy](https://mlsanity.com/paper/2108.07664/) (2021)
- [Sequential metric dimension for random graphs](https://mlsanity.com/paper/1910.10116/) (2019)

## Built on by (most cited first, 1 of 1)

- [Optimal Reconstruction from Linear Queries](https://mlsanity.com/paper/2605.19625/) (2026)

## Abstract (arXiv)

Consider the task of locating an unknown target point using approximate distance queries: in each round, a reconstructor selects a query point and receives a noisy version of its distance to the target. This problem arises naturally in various contexts ranging from localization in GPS and sensor networks to privacy-aware data access, and spans a wide variety of metric spaces. It is relevant from the perspective of both the reconstructor (seeking accurate recovery) and the responder (aiming to limit information disclosure, e.g., for privacy or security reasons). We study this reconstruction game through a learning-theoretic lens, focusing on the rate and limits of the best possible reconstruction error. Our first result provides a tight geometric characterization of the optimal error in terms of the Chebyshev radius, a classical concept from geometry. This characterization applies to all compact metric spaces (in fact, even to all totally bounded spaces) and yields explicit formulas for natural metric spaces. Our second result addresses the asymptotic behavior of reconstruction, distinguishing between pseudo-finite spaces -- where the optimal error is attained after finitely many queries -- and spaces where the approximation curve exhibits nontrivial decay. We characterize pseudo-finiteness for convex Euclidean spaces.