Research map / Learning theory and algorithms / Sample complexity
Reconstruction and Secrecy under Approximate Distance Queries
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes the limiting optimal reconstruction error in the noisy distance-query game via the Chebyshev radius (diameter-radius profile), and studies pseudo-finiteness, showing convex Euclidean sets of dimension ≥2 are not pseudo-finite for small delta.
Problem
Locating an unknown target point in a metric space using approximate (multiplicative and additive noisy) distance queries; determining the optimal limiting reconstruction error and how fast finite-query error converges to it.
Approach
Shows the limiting optimal error equals the diameter-radius profile e_X((2+eps)delta), i.e., the worst-case Chebyshev radius over sets of bounded diameter, for totally bounded spaces; uses hypergraph/Hausdorff-metric compactness for right-continuity and an explicit responder strategy that preserves shrinking neighborhoods of regular simplices (with rotations when eps=0) to rule out pseudo-finitene
Key results
- OPT_X(eps,delta) = e_X((2+eps)delta) for totally bounded X, with (1/2)(2+eps)delta <= OPT <= (2+eps)delta when the distance (2+eps)delta is realized.
- The real line [0,1] is (0,delta)-pseudo-finite but not (eps,delta)-pseudo-finite for eps>0.
- Bounded convex subsets of R^n with dimension at least 2 are not pseudo-finite for sufficiently small delta (except eps=0 and dim 1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow positive multiplicative distortion ε instead of ε = 0 | Reconstruction game on [0,1] · [0,1] with Euclidean metric | pseudo-finiteness | Hurt |
| Use a bounded convex Euclidean space of dimension greater than one | Reconstruction game · Bounded convex X ⊂ ℝⁿ, sufficiently small δ > 0 | pseudo-finiteness | Hurt |
| Use ε = 0 and dimension one rather than positive multiplicative distortion or higher dimension | Reconstruction game on bounded convex Euclidean spaces · Bounded convex X ⊂ ℝⁿ, sufficiently small δ > 0 | pseudo-finiteness | Helped |
Surprising findings
- Bounded but not totally bounded spaces (e.g., infinite discrete space) let the responder force error equal to the diameter, so total boundedness is necessary.
- Random-noise responder strategies do not suffice to rule out pseudo-finiteness; a calibrated simplex-preserving strategy is needed.
Limitations
- Rate of convergence for delta>0 is not matched by upper bounds; only lower bounds (exponential or double-exponential) are established.
- Open question whether totally bounded pseudo-finite spaces must be finite.
- Results are theoretical; no experiments.
Experimental setup
Metrics: reconstruction error
Builds on: sequential metric dimension Dinur-Nissim reconstruction
Closest papers by meaning
- Optimal Query Complexity of Secure Stochastic Convex Optimization (NeurIPS 2020 · similarity 0.84)
- On Differential Privacy for Adaptively Solving Search Problems via Sketching (ICML 2025 · similarity 0.82)
- Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization (NeurIPS 2024 · similarity 0.82)
- Perturb-and-Project: Differentially Private Similarities and Marginals (ICML 2024 · similarity 0.82)
- Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness (ICLR 2025 · similarity 0.81)
- Optimality of Matrix Mechanism on $\ell_p^p$-metric (ICLR 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.