Reconstruction and Secrecy under Approximate Distance Queries
Authors: Shay Moran
Elizaveta Nesterova
Venue: NeurIPS 2025 spotlight ()
Keywords: Learning Theory
Active Learning
Similarity and Distance Learning
Information Theory
Privacy
Primary area: theory
TL;DR: We prove tight asymptotic limits for reconstructing a hidden point from noisy distance queries and give a dimension-based criterion for when metric spaces are (non)-pseudo-finite.

Abstract: Consider the task of locating an unknown target point using approximate distance queries: in each round, a reconstructor selects a reference point and receives a noisy version of its distance to the target. This problem arises naturally in various contexts—from localization in GPS and sensor networks to privacy-aware data access—making it 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, to all totally bounded spaces) and yields explicit formulas for natural subsets of the Euclidean metric. 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 a nontrivial decay. We characterize pseudo-finiteness for convex subsets of Euclidean spaces.

Reconstruction and Secrecy under Approximate Distance Queries
Shay Moran
Elizaveta Nesterova Department of Mathematics, Technion
Department of Mathematics, Technion Department of Computer Science, Technion Department of Data and Decision Sciences, Technion Google research
Abstract
Consider the task of locating unknown target point using approximate distance queries: in each round, reconstructor selects reference point and receives a noisy version of distance to the target. This problem arises naturally in various contexts contexts-ranging 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 limit information disclosure, c.g., for privacy or security reasons).
study this reconstruction game through learning-theorele lens, focusing on the rate and limits of the best possible reconstruction error. Our first result provides tight geometric characterization of the optimal error in terms of the Chebyshev radius, classical concept from geometry. This characterization applies to all compact metric spaces fact, even to all totally bounded spaces) and yields explicit formulas for natural metric spaces. Our second result addresses the asymptotic bchavior 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-fmiteness for convex Fuclidean spaces.
Introduction
In the reconstruction game, reconstructor seeks to locate unknown point æ² in metric space (X, distx) using sequence of approximate distance queries. In each round, the reconstructor selects query point Si E X and receives response de that approximates the true distance dist (gt, x*), The approximation is controlled by two error parameters: 2 0, which bounds the multiplicative error, and 2 0, which bounds the additive error. Specifically, the response satisfies d, = dist x*), where
T
means that x S (1 + c)y + and y S (1 + c)x +
After bounded number of such queries, the reconstructor outputs guess & X and aims minimize the reconstruction error (ă,
This simple game arises in a wide range of natural scenarios. In privacy-pressevinng data analysis, it models the trade-off between utility and privacy: a responder must answer queries while protecting sensitive data, in the foundational work of [Dinur and Nissim 2003 that initiated the study of differential privacy"] In computational geometry, related questions arise when inferring geometric structures from noisy measurements (Disser and Skiena 2017]. In remote sensing, satellites and sensors reconstruct physical information- as terrain or atmospheric properties-from indirect and error-prone signals [Twomey] 1977]. Similar structures also appear in learning theory: for instance, hypothesis selection and distribution learning via statistical queries can be framed as reconstruction problems suitable metric spaces.
'The reconstruction model studied by Dinur and Nissim uses counting (or linear) queries, but is essentially equivalent to our model with distance queries. elaborate on this connection Example
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

The reconstruction game captures natural tension between two objectives: recovering hidden information and limiting what can be revealed. From the reconstructor's 's perspective, the task is to approximate unknown point from noisy distance measurements. This challenge arises in variety of applications, including navigation, search-and-reseue, and remote sensing, where inference must he made under uncertainty. On the other side, the responder may wish to share useful information while restricting what can be inferred- whhether for reasons of privacy, security, or resource constraints. This interplay between noisy access and limited disclosure makes the model relevant across several domains.
While this framework treats the reconstructor and the responder symmetrically, assigning equal roles to both players, our technical results are directed toward understanding the limits of what the reconstructor can achieve. We present two main contributions:
We characterize the optimal approximation error that the reconstructor can guarantee in the limit, the number of queries tends to infinity. This emror depends on the metric space and the approximation parameters e and 6, and our characterization applies all totally bounded metric spaces. The result is expressed in terms of classical geometric quantity: the Chebyshev radius. This limiting error plays a role analogous to the Bayes optimal error in statistical learning: it captures the best achievable performance in the presence of noise, regardless of the specific strategy or number queries. Our result provides a geometric characterization and interpretation of this optimum in the context of the reconstruction game.
Limit of optimal reconstruction (Theorem 2).
Pseudo-finite Spaces (Theorem 6). Beyond the limiting error, a central question concerns the rate which this optimum is approached as function of the number of queries. This question is inherently rich and depends delicately on the geometry of the space. It is analogous to the study of learning curves in statistical learning theory, which quantify how the performance of learner improves with more data. We initiate the study of this question in our setting by identifying and analyzing a fundamental distinction between pseudo-finite spaces-where finitely many queries suffice to reach the optimum-and and spaces where convergence is gradual. We show that this notion already subtle and nontrivial, and we provide a characterization of pseudo-finitema for convex Euclidean spaces.
1.1 Problem Setup and Main Results
We now define the reconstruction game, formal interaction between two players: reconstructor (RC) and a responder (RSP). The game takes place in metric space (X, distx), where X is the domain and dist X X + Rgo is distance function. The interaction is governed by two error parameters: 2 0, controlling multiplicative distortion, and 8 2 0, controlling additive distortion.
The Reconstruction Game
The game is parameterized by c, 5 2 0, and is played over T rounds in metric space (X, distx). ) Each round f 1...., proceeds as follows:
1. The reconstructor submits query point E X.
2. The responder returns value d, which approximates the true distance some secret point.
The responder must ensure that all answers given in the game remain jointly consistent with at least one point x². That is: (3x* E X)(VI < T) de =e,s distx (gt, x²), where =,, y means that de S (1 + didis (g., x²) + d and dis x²)=== < (1 + e)d, +
At the end of the game, the reconstructor outputs final guess रτ E X. The reconstruction error is defined as the worst-case distance consistent point: sup,. dist x (#T, where x² ranges over all consistent points.
The reconstruction game studied in this work generalizes task of determining the sequential metric dimension (SMD), which was originally introduced in the noiseless setting for graphs by /Seaee 2013). The SMD captures the minimum number exact distance queries required to identify an unknown point exactly, and has been studied in finite metric spaces induced by graphs [Bensmail

---

et al. 2020 Odor and Thiran 2021 Tillquist et al. 2023]. with particular emphasis on the gap
between sequential and static metric dimension
As another example, the counting-que querr model introduced by Dinur and Nissim 2003 in their foundational work can also be naturally viewed as special case of our reconstruction game on the Boolean cube endowed with the Hamming metric:
Example (From counting queries to distance queries). In the counting-ques query model (Dinur and Nissim 20033, the dataset is binary vector D = (d1,...,d,) (0, 1)". At round t I,..., T,
the reconstructor chooses a subset qt S [m]] and receives
0t Σdd d. + ne, EEq.
Iee S 8.
This game is not syntactically a metric-distanee game, yet is equivalent to our distance-quer model on the Boolean cube with the Hamming metric, in the sense that counting queries and Hamming- distance queries simulate each other with at most a two-query overhead per round. Full details of the simulation appear in Appendix F3
Example 30
Priori vs. A Posteriori Responder. There are two natural variants of the reconstruction game, which differ in when the responder commits to the secret point.
In the priori version, the responder selects secret point x E X at the beginning of the game and must answer all queries consistently with that fixed point. In contrast, the posteriori version (which we adopt) allows the responder to wait until the end of the game when the reconstructor selects her guess Sr, before selecting the secret point x".
Note that for deterministic reconstructors, the a priori and a posteriori models are equivalent: any a posteriori responder can be simulated by an a priori one, simply by anticipating all queries of the reconstructor and precomputing a worst-case consistent point in advance. "Deterministic" here refers only to the absence of internal randomness and does not restrict adaptivity; deterministic reconstructor may choose each query based on the entire interaction so far, whereas "non-adaptive" denotes the special case in which all queries are fixed in advance.
Remark. We define the game using the a posteriori model because our results focus on the capabilities of the reconstructor in the worst-case setting. From this viewpoint, the most meaningful formulation is one where the responder is allowed maximal flexibility, making the task of reconstruction as difficult as possible.
1.2 Optimal Reconstruction Distance
At each point in the game, the sequence of region-the set of points in X that are consistent with all previous answers under the error model. The size and geometry of this region reflect the remaining uncertainty about the secret point. From the reconstructor's perspective, the goal is make this region as small as possible, ideally identifying a point that is close to every element in it. We measure the performance of a reconstruction strategy by the worst-case distance between the output द and any point in the feasible region. The key quantity we study is the optimal worst-case guarantee achievable by the reconstructor after T queries, denoted by
pairs received so far determines a feasible
O 8) = inf sup sup distx (ær, x). RC RSP f
Here, T S X is the feasible region the set of points that remain consistent with the transcript (i.e., the sequence of queries and responses) (gg,, d
(l,., rz rT)) {x X for all SiST: distx = r:}
(2)
The infimum ranges over all strategies employed by the reconstructor, and each such strategy is evaluated in the worst case: against the most adversarial responder strategy (subject to consistency), and with respect to the most distant feasible point. For randomized reconstructors, we interpret Equation (I) by replacing dist x (ør, .r) with E Eldistx (2r, x)). where the expectation over the
'The static metric dimension the minimum number of reference points needed to uniquely determine any point in the space based on its distances to those references. It corresponds to the non-adane adaptive variant of our setting, where all queries are fixed in advance.
3

---

intermal randomness of the reconstructor. For simplicity of presentation, we assume the reconstructor deterministic; however, all of our results and proofs extend to the randomized setting.
Much of our focus will be on understanding how this function behaves as + co, and how depends on the geometry of the underlying metric space X. Our first main result concerns the asymptotic
quantity
OP
lim (P,,
T T-
which captures the best reconstruction error the reconstructor can guarantee in the limit, as the number of queries grows
Chebyshev Radius. To characterize OPTx (e, 5), we rely classical geometric quantity called the Chebyshev radius, which captures how well set can be enclosed by ball. Let (X, distx) ) be metric space, and let 0 be parameter. For any subset S C X, we denote its diameter by diam := supx.yes distx(I: y). The Chebyshev radius of S, denoted r(S), is defined as
r(S) == -inf sup [dist x (z, y)],
=EX yES
that is, the smallest radius for which some ball centered in X contains all of S.
We will also rely the following quantity that captures the worst-case relationship between sets of diameter at most a and the radius of their smallest enclosing ball:
ex (a) ==
sup r(8).
S: d:dimm()): Sa)
For example, in Euclidean space (R", f2), it is known that for all a > 0, ex(()
2n+IJ Or as
shown, for instance, in [Blumenhhal [9700]s 's monograph.
Before stating our first main result, recall standard notion from metric geometry. metric space (X, distx) is said to be totally bounded if for every >> O. there exists finite cover of X by balls of radius This a common weakening of compactness that still ensures many desirable finiteness properties. As we will see in Section 2 this assumption is necessary for the theorem's 's conclusion; without the game can trivialize, allowing the responder force an approximation error equal to the space's 's diameter.
Tight Error via Chebyshev Radius
Theorem 2. Let X be totally bounded metric space. Then, for any c, 5 2
OPTx(c,8) = =e ((2 c))).
Moreover, the distance (2 e)6 is realized in X, i.e., there exist pair of points at this distance, then
(2 e)6 < (PTx(e, (2 e)ā.
2
This result expresses the limiting reconstruction error in terms of the function (.), which captures the worst-case Chebyshev radius over sets of bounded diameter. While the definition of ex e) may seem somewhat cryptic at first glance, it is often closely tied to the scale of noise introduced by the responder. Specifically, in many natural spaces, it holds that
x 6) = ((2++e)0) e))).
This follows from the next general observation, which bounds the ratio between the Chebyshev radius and the diameter of a set in any metric space.
Observation 3. In any metric space (X, distx) ) and every a > 0 which is realized as distance in the space. Ja < ex(a) < a. The upper bound follows follows because any set of diameter a can be trivially enclosed in ball of radius a. The lower bound holds because no ball of radius < a:/2 can contain two points at distance a.
The bounds a/2 and a are tight: they are attained by natural totally bounded metric spaces, as we will demonstrate through examples in Section
1 As shown in Appendix D specifically in Claim 13 the function OT, 6) is monotonically non-
increasing in 7", so this limit always exists.

---

1.3 Excess Reconstruction Error
From a barming-thheoreti perspective, the limiting enror OPTx (c,5) plays a role analogous to the Bayes optimal error in statistical learning: it represents the best achievable performance under the constraints of the model. This motivates the study of the excess reconstruction error- the difference between the error achieved after T queries and this asymptotic optimum: OPTx (T, c, 0) x 6). Understanding the rate at which this quantity decays as 7 + oo is a natural next step. This question is generally quite challenging and depends intricately on the geometry of the underlying space. As a first step in this direction, our second main result focuses on a basic dichotomy: between spaces where convergence the optimal error is trivial-i.e., achieved after finitely many queries-and all others. We formalize this notion through the following definition:
Definition 4 (Pseudo-fini) finite Spaces). A metric space (X, (X,iis)) is said to be (c, 8)- if there exists a finite constant T < 00 such that
OT, = (P) for all T Tx,,,6-
It is easy to see that any finite metric space is (c, d----))doo-finng finite for all values of c, 0 2 0: the reconstructor can simply query every point in the space; and no additional information can be obtained once all points have been queried. Another example of pseudo-finiteness is provided by fiite-dimeeniionl Euclidean spaces. The space R" is (0, O--peudooffiiic " since the reconstructor can determine the exact location of the secret by querying n + affinely independent points (see, e.g. [Tillquist et al. 2023) ). In contrast, we will see in the next section an example of a totally bounded metric space that is not (0, 0) p--puudo-fiiite.
We now turn our attention to Fuclidean spaces. Naturally, we begin with the simplest case: the real line. Despite its simplicity, the real line exhibits nuanced ppeudo-finttnnes behavior that depends on the error parameters. In particular, pseudo-finite finiteness holds when there is no multiplicative noise, but breaks down as soon as any multiplicative distortion is allowed:
Proposition 5 (Pseudo-initeness. of the real line). Let X = 1. S Th equipped with the standard Euclidean metric. Then: (i) For every 5 2 O, the space X is (0, pseuudo-eoe (ii) For every e O and every 5 2 0, the space X is not (c, j---seudo-fiite.
This proposition follows from our general result below (Theorem 6.. but can also be derived more directly in this special case. When O, the reconstructor can query one of the endpoints @1 E (0, 1): the response confines the secret to an interval of length 26, and outputting its midpoint yields an error of at most 8, which is optima When > O, the responder can use a binary-search-liäe strategy to ensure that the feasible region always contains interval of length strictly greater than (2 + e)6, thereby preventing the reconstructor from reaching the optimum in finitely many steps.
How about higher-dimentn dimensoaimensional Euclidean spaces- do they exhibit the same behavior as the real line finiteness? Our second main result addresses this question for the class of convex subsets of Fuclidean space. To state it, we recall that the dimension of convex set X C TR refers to the dimension of its affine span, i.e., the smallest affine subspace containing X. In higher dimensions, this nuanced behavior disappears: convex subsets of IR" with dimension at least two are never pseudo-finite, regardless of the values of c and 8, as long as they are sufficiently small compared to the diameter.
with respect pseudo-fintennss?
Finidd--ii in Convex Euclidean Spaces
Theorem 6. Let X C R" be bounded convex set equipped with the Euclidean metric such that dim X > O and let 2 O. Then, for all sufficiently small 8 > 0, the space X is not (e, -seudooooff,,, except in the case where O and dim X 1.
The proof of this result is surprisingly delicate. At a high level, one might expect that a responder could simply inject random noise into the true distances, thereby ensuring that the reconstructor improves only gradually over time. However, such a strategy does not suffice to rule out pseudo- finiteness: to do so, one must ensure that for every reconstructor strategy, the reconstruction error
"Note that noise plays an important role in this example: R" is pseudo-finit whenever the noise
parameters are nonzero and n 2 2.
"The optimality of the error å on the interval, for sufficiently small 8, follows from the fact that e (6) = 8 together with Theorem
5

---

remains strictly larger than the optimal limit for any finite number of queries. This requires carefully calibrated noise that not only misleads the reconstructor but also guarantees that the resulting feasible region strictly contains set of points forming an extremal body one that achieves the maximal Chebyshev radius under a bounded diameter constraint.
In fact, the lower bound on OPTx (e, 6) established in Theorem 2 is implicitly used in proving Theorem as it certifies the minimal size of the region that the responder must preserve.
Theorem Remark. The proof of Theorem provides two lower bounds on the convergence rate of OPT(T,, e, 6):
exponential in 'I for E + and double-exponentiad for e = O. On the upper-bound side, obtaining a matching rate for 8 appears nontrivial, and the optimality of the known lower bounds remains unclear.
O. and a matching exponential upper bound follows from a standard grid-refnement argument: the reconstructor queries a uniform grid of fixed size (depending only on the dimension), selects the grid point with the smallest reported distance, then recenters a new sized-size grid at that point and rescales to smaller neighhorhood. Iterating this geometrically shrinks the feasible region, yielding an exponential upper bound on (T,,
In the purely multiplicative case 5 = 0, however, XPTx
Organization. In the next section (Section 2), analyze and discuss basic examples of the reconstruction game. In Section we provide high-level overview of the main technical ideas used in our proofs. For space reasons, the related work deferred to Appendix A which surveys relevant literature from learning theory, privacy, and geometry. The complete formal proofs are presented in Appendices B through E Appendix F collects technical lemmas from geometry and topology and provides full proofs of the examples sketched in Section [ along with additional examples that further clarify the game.
2 Examples
This section presents illustrative examples of the reconstruction game in variety of metric spaces. These examples shed light on different aspects of the problem, including the necessity of the assumptions in our main theorems and the range of geometric behaviors that can arise. They also help clarify the role total boundedness in Theorem 2 and lead naturally to an open question about pseudo-finite totally bounded spaces. In contrast to the following aettonss-hich focus more heavily on Euclidean metric spaces in the context of Theorem 6 -tis section is technically lighter and features some more "exotic" spaces. Full proofs of the examples discussed here appear in Appendix
F33
2.1
Total Boundedness in Theorem 2
The first main result (Theorem characterizes the limiting reconstruction error in terms of the Chebyshev radius function e (.), assuming that the metric space X is totally bounded. The following examples illustrate that this assumption is essential: if total boundedness is lifted, even seemingly natural spaces allow the responder to prevent the reconstructor from obtaining any meaningful approximttion-speciccllllll an error bounded away from zero, even infinite.
Example 7 (Unbounded Space: The Real Line). We begin with simple case: R with its standard Euclidean metric. This spuce is not bounded (and hence not totally bounded), and the responder can exploit its unboundedness to maintain exiremely large feasible regions throughout the game. A formal proof is given in Appendix F.3
The previous example showed that in some unbounded metric spaces, such as R, the responder can force the reconstruction error to be arbitrarily large. This naturally raises the question: could boundedness alone suffice for the conclusion of Theorem 2 That is, can strengthen the theorem by replacing total boundedness with the weaker assumption of boundedness? The answer is negative:
Example (Bounded but Not Totally Bounded: Discrete Countable Space). Consider the space X = N. the set of natural numbers equipped with the discrete metric: dist, x ji, = 0 if j. and distx (i.j) = 1 otherwise. This space is bounded (diameter 1) but not totally bounded.
Now, note that even if the responder must be fully honest (i.e., e = = 0), can always answer d, This ensures that the feasible region after every round remains infinite subset of X in which all

---

points are pairwise at distance 1. Consequently, the responder can choose a consistent point of distance 1 from the point guessed by the reconstructor, yielding an approximation error equal the diameter of the space.
2.2 Eseudo-Finiteness
Although our main result about pseudo-finiteness focuses convex Fuclidean spaces, the phe- nomenon is more subtle in general metric spaces. In this section, we present three infinite metric spaces. Two of these spaces are (e, (ese)dsoooo- for all values even (0, O)-pseudo-finite These examples highlight the diversity of possible behaviors in general metric spaces and motivate an open question concerning the structural nature of pseudo-finitenes. in totally bounded spaces.
6 2 0, while the third is not
Example 9 (Sparse Subsets of the Real Line). Ler X = [0] f22 : e C with the standard (c, ----ssuuo-fiiitt for every c, 5, 2 0.
Euclidean metric. Then X is
To see this, let the reconstructor begin by querying the point qı = 0. The response di yields a feasible region consisting of a finite subset of X, whose size is bounded by a constant N(c, that depends only on the noise parameters (and not on the specific value of dz). This is because the set X, when viewed monotone sequence, grows asymptotically faster than any geometric progression. After this initial step, the reconstructor continues to query all points in the feasible region to identify an optimal approximation.
The above example is unbounded. This raises the question of whether there exist bounded infinite spaces that are (e, pspeududofiietee for all e, ó. The next example shows that the answer is yes.
Example 10 (Countable Discrete Metric Space Revisited). Recall the space X = N with the discrete metric: dist x (ar, y) = 0 i = y. and otherwise. This space is bounded, with diameter As previously discussed (see Example 8. we have OPTx(e, 6) for all 8 2 O. Therefore, the reconstructor can achieve optimal performance without submitting any queries, simply by outputting any fixed point in the space. Thus, X is (e, 8) --seedoo-ffiite for all e, 0.
These two examples motivate the following open question: similar behavior occur in totally bounded spaces?:
Open Question 11. Let X be totally bounded metric space. Are the following two statements equivalent? (i) X is finite. (ii) X is (c. 50--)sddoo-ffit finite for all e, 8 2
We conclude this section by presenting totally bounded metric space that not (0, 0)- (0--puuuoo-finee Example 12 (Infinite binary strings). Let X {0, 13 l be the space of infinite binary sequences, equipped with the standard ultrametric Idefined by d(a, 3) 2 where is the first index at which aj # By. Then X is compact metric space that is not (0, -sspuuuuo-ffiite. The proof appears in Example 28
3 Technical Overview
In this section, outline the key ideas behind the proofs of Theorem 2 and Theorem 6 complete proofs are deferred to Appendices and B To keep the exposition focused on the central arguments, omit technical complications arising from cases where suprema or infima are not attained. These can be handled with standard limiting arguments but would introduce additional notation and obscure the main ideas.
3.1 Proof of Theorem
We begin by recalling the core assertion of Theorem It characterizes the optimal reconstruction eтror OPT (c, 8) in terms of the geometry of the metric space and the noise parameters and 5. Specifically, asserts that OPT x (e, 5) 5) equals the maximum Chebyshev radius among all subsets of X with diameter at most (2 + e)o: OPTx = ex ex ((2+
'This metric satisties the ultrametric inequality: d(x, 2) < max ((xx, y), ddy,))), which is stronger than the standard triangle inequality. It implies, for instance, that all triangles are isosceles with the two longer sides equal.
7

---

To prove this, we begin by analyzing an idealized setting in which the reconstructor is allowed to query all points in the space. Of course, this unrealistic infinite spaces- but serves as a useful thought experiment for understanding the limits of reconstruction.
Each query-answer pair (q:r) determines feasible region @ [g, r)), which consists of all points whose noisy distances to are (e, -i-ddistinguishabll from r. The intersection of all these regions gives the overall feasible region of the interaction, denoted by Φ := ((g, rolvex).
Upper Bound. In the idealized case where all points in the space are queried, a simple yet insightful argument shows that the diameter of the feasible region & is at most (2 + +)ō. Indeed, for any two points A, B E h since B was queried and A remained feasible, the reported noisy distance must not exceed 6, and therefore the true distance distx (A, B) cannot exceed (2 + ejo. By letting the reconstructor output the Chebyshev center of 4. the reconstruction error is at most ex ((2 + e)6).
When only finitely many queries are allowed, however, the reconstruction error can be significantly larger than in the idealized case; shown in Section 2.1 there exist spaces in which this discrepancy is arbitrarily large.
Nevertheless, if the metric space X is totally bounded, the reconstructor can approximate the idealized strategy arbitrarily well: by querying all points in a sufficiently dense finite cover, one ensures that the feasible region has diameter arbitrarily close to (2 + +).. Such a finite cover exists by definition: a metric space is totally bounded if, for every a > 0, admits a finite a--over-thoe is, a finite subset such that every point in the space lies within distance of some point in the cover. Denote by Na the number of points in an a-cover of the metric space X. As illustrated in Figure 2 after No queries the reconstructor can guarantee that the diameter of the feasible region is less than (2 + c) + a', where a' = ((1 + 2)² + 1)a. Hence, by outputting the Chebyshev center of the feasible region, the reconstructor ensures that the worst-case error after Na queries is at most e ((2 + c) + a'), by the definition of ex (B) as the maximum Chebyshev radius over all subsets of X with diameter at most B.
might be tempting to conclude that we are done, since the function ex appears to continuous. However, this inference is, in general, false: for arbitrary metric spaces, e need not be continuous. For instance, in finite metric spaces the function e is not continuous.
On the other hand, it can be shown that for totally bounded metric spaces the function e is right- continuous, which is sufficient for establishing the desired upper bounds. Nevertheless, proving right-continuiy remains nontrivial in general: there exists a non-totally bounded metric space for which the corresponding function e fails to be right-continuous (see Example 29 in Appendix (F.3).
We prove that the function ex is right-continuous for totally bounded metric spaces using the theory of hyperspuces. Namely, given metric space X, one considers the space of (nonempty) compuct subsets of X, denoted KC(X) equipped with metrics induced by the metric on X. The most standard choice is the Hausdorff metric: for subsets S1, S2 S
(H( S2) = max sup inf dist (z,y), sup inf distx (z, v). ( wES,
vES, wes,
variety of classical results are known for (KC(X), dz): for instance, when X is compact, the hyperspace XCXX is compact as well. This is classical fact in metric topology; see, e.g., Illanes and Jr. [Teereee 3.5].
Both the diameter and the Chebyshev radius of a set are continuous functions on (K(X), dg) ): this follows by bounding their variation in terms of the Hausdorff distance (see the detailed argument in Appendix F.I.. Together with the compactness of (KC()), dx). this yields, via a compactness argument, that e is right-continuous for compact metric spaces. For a totally bounded metric space X, in turn, one can show that ex = ex. where X denotes the completion of X. Since the completion of totally bounded metric space is compact by the classical Heine-Borel characterization for metric spaces (compact < complete and totally bounded), follows that ex is right-continuous for totally bounded metric spaces as well. All techniques and formal proofs for the right-continuity of ex are presented in Appendix F.T The full proof of the upper bound appears in Appendix C.2
The erucial observation is that at the beginning of the game, the responder may select any subset S C X of diameter most (2 + e)o, and maintain the invariant S C Φ throughout
Lower Bound.
8

---

the interaction: In response to each query g, the responder identifies point Smin E S that minimizes the distance to 9, and returns the perturbed value
r y: (1 + e) distx (q, Smin) + 6.
simple calculation, which relies only on the triangle inequality, shows that every 8 E S satisfies distx (g, s) Fe, r, and hence S remains feasible.
After the interaction concludes, given the reconstructor's final guess, the responder can choose secret point at distance no less than r(S) inside S C Φ. This ensures that no reconstructor can guarantee an error smaller than ex ((2 + =)6). A precise description of the responder strategy that preserves an extremal set is presented in Appendix C.I
query
(2 + c)6
Oa-hall
net point
Chebyshev center
query
a' ((1 + +e + 1)a
Figure I: Feasible region c (blue) of the ideal-
Figure 2: Feasible region & (blue) of the finite interaction
ized case
3.2 Proof of Theorem 6
We now turn to the proof of Theorem 6 which establishes a dichotomy for pseudo-finiteness in bounded convex subsets of Euclidean space. Specifically, the theorem states that bounded convex set X C. IR" is (e, d)--suudo-finite if and only if dimmX) = 1 and e = O. In all other cases-namely, when dim 1 e 0-the reconstruction error cannot reach its optimal value in finitely many steps.
One might hope to prove non-pseudo-finteee finiteness by designing responder strategy that gradually shrinks the feasible region-es e.g., by adding uniform random noise to the true distance in each response. However, this naive approach fails to guarantee the desired behavior: in particular, it does not ensure that the reconstruction error remains strictly greater than the optimum OP ō) at all finite T. In fact, such strategies may lead convergence toward strictly smaller value, and therefore not optimal for the responder.
To overcome this, proof explicitly constructs responder strategy that, every round, ensures the feasible region contains a subset guaranteeing that the reconstruction error remains strictly larger than the optimum OPT(e,, 8) + ar,, where oer 0 depends only the number of rounds.
This mirrors the bound strategy used in Theorem 2 where the responder preserved an extremal set to ensure the Chebyshev radius never fell below OPT(c, 6). However, to prove non-pseudo- finiteness, it is not sufficient to preserve region whose radius merely equals the optimum. Instead, we must ensure that the feasible region's Chebyshev radius remains strictly greater than the limiting value for all finite
To accomplish this, our strategy preserves an a-neighborhood of the vertices {a, ) of some regular simplex A7l denoted A... where 0 depends only on the number of rounds T.. Formally, the a-neighborhood of the simplex A with vertices {z; J is defined as
A_ B(z,,))
B( a) denotes the Euclidean ball of radius centered at zT,
This ensures that the feasible region contains regular simplex of diameter (2 + e)ō + 2(x+1)
which in turn implies that its Chebyshev radius is at least OPT(E, 8) +
Our strategy proceeds as follows. Assume that round t the feasible region already contains an ny-ieihboourhooo of regular simplex A. Upon receiving the next query qr. we pick a radius a++1
'hroouhoout this work. by "simplex" we usually mean the set of its vertices that is. n + 1 affinely independent points in the Euclidean space X of dimension

---

determined solely by e, 5; then we reply with an appropriate noisy distance rs and, if necessary. replace A by a new extremal simplex A' so that
(ar) C (A)a, and (A')a C (updated feasible region). This step is then repeated indefinitely, keeping the Chebyshev radius strictly above OPT. Conse- quently, X'' is not pseudo-finite.
The main challenge is provide uniform lower bound ag that depends only the round t, and not on the specific query q.- We note in passing that it is relatively easy to give a bound on 42411 that depends on both and the query qr: however, such a bound is insufficient for our purposes, it does not yield a general lower bound on OPT, valid for all reconstructor strategies, which is essential for ruling out neeudo-finteenss.
On the other hand, finding the uniform bound requires handling each query type with care, since for some queries it is easy obtain sufficiently large neighborhood of some simplex A contained within the neighborhood the previous one, while for others it requires a more delicate geometric argument.
Determining the Maximal Surviving Neighborhood. To address the challenges above, we ask: under what conditions does there exist answer that the responder can give to the query q such that the a-neighborhood (see Eq. (3) of A remains entirely within the feasible region?
The answer is follows: there exists such response if and only if (Aa) S rg (Aa), where rg places the farthest point of A. on the outer boundary the feasible region, and r max places the nearest point on the inner boundary (see Fig. Fig.
S Smax
S max
min
min
Figure 3: ((g, min) (blue)
Figure 4: 2(q, y max) (orange)
The larger the radius of the neighborhood A.. the smaller the gap yaa pim becomes. Solving the equation ymax (Ax,) min (A.)) = 0 for a yields the exact value ax (A, q) of the largest surviving neighborhood upon querying q. It is useful to view the quantity or (*, q) as function on the space of regular simplexes. The derivation of the exact formula for a* is presented in Appendix D
Additive-Only vs. Multiplicative Noise. Both responder arategies-addiiive--oo noise-rely on the same principle: for a fixed simplex and a target neighborhood radius 0++1, together with the neighborhood radius 0ę 0++1 from the previous round, we partition the space into (A, 0c+1) (441) ]-good and bad regions. A query point is called good if there exists a response that preserves a neighborhood of radius least 0x++ of A within the feasible region; equivalently, if the maximal surviving neighborhood satisfies at [A, q) 2 ac+1- Otherwise, q is bad.
and mixed-
When is good, the responder maintain the a++1 neighborhood of the current simplex A inside the feasible region. The critical difference between regimes arises when q is bad. In this case we should find another regular simplex A' in the ay-neighborhood of A such that the point g is now (A' (1+1)== gooo.. In the multiplicative case (e > 0), the responder can translate the simplex A slightly away from the query point q ensure that a (A', Z 0++1 and that A C
In contrast, when c = 0. translations of A within its ay-neighborhood do not substantially change a (*) q). To achieve significant increase in a (*(xxq) q) in this case, we rotate the simplex Á. To do this successfully, the rotated simplex must preserve the identity of the closest and farthest points from the query, which requires a careful geometric analysis.
Appendix F.2 we develop the tools necessary to carry out this strategy. In dimensions n 2 2, rotations allow us to maintain surviving neighborhood indefinitely. In one dimension, however-wher nontrivial rotations are not possible- this strategy fails for good reason: one-dimensional intervals are pscudo-finite.
10

---

Acknowledgments and Disclosure of Funding
We thank Nikita Gladkov for insightful discussions related to the problems studied in this work.
Shay Moran is Robert J. Shillman Fellow; he acknowledges support by ISF grant 1225/20, by BSF grant 2018385, by Israel VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the the European Union (ERC, GENERALIZATION, 101039692). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency, Neither the European Union nor the granting authority can be held responsible for them.
References
B. Balle, G. Cherubin, and J. Hayes. Reconstructing training data with informed adversaries. In 2022 IEEE Symposium Security and Privacy (SP), pages 1138-1156. IEEE, 2022.
J. Bensmail, D. Mazauric, M. Inerney, N. Nisse, and Pérennes. Sequential metric dimension. Algorithmica,, 82(10):2867-290,, 2020. doi: 10.1007/004533-00000777--55 URL httpt://haal sciencee/hal-00177766991
L. M. Blumenthal. Theory and Applications of Distance Geometry. Oxford University Press, Oxford,
2 edition, 1970. Originally published 1953.
E. Cohen, H. Kaplan, Y. Mansour, S. Moran, K. Nissim, U. Stemmer, and E. Tsfadia. Data reconstruction: When you see and when you don't. In R. Meka, editor, 16th Innovations in Theoretical Computer Science Conference, ITCS 2025, January 7-10, 2025, Columbia University, New York, NY, USA, volume 325 of LIPIcs, pages 39:1-39:23, Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2025, doi: L0.4230/LIICSSSICCS.AA 2025.39, URL https: http:///oooooo//.1000000.0
LIPIcs. ITCS. 2025.39
R. Cummings, S. Hod, J. Sarathy, and M. Swanberg. Attaxonomy: Unpacking differential privacy guarantees against practical adversaries, 2024.
I. Dinur and K. Nissim. Revealing information while preserving privacy. In F. Neven, C. Beeri, and Symposium
T. Milo, editors, Proceedings of the SSennt--econd//i ACM SIGACT-SIGMOD-SIGGA on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA, pages 202-210. ACM, URL BtRL::tts:://do org/oo///// 1145/773153 773173
2003. doi: 10. 10.11457731533773177
Y. Disser and Skiena. Geometric reconstruction problems. In Goodman, O' D'Ruurke, and C. Tóth, editors, Handbook of Discrete and Computational Geometry, Third Edition, chapter 35. CRC Press LLC, 3 edition, 2017.
C. Dwork and S. Yekhanin. New efficient attacks on statistical disclosure control mechanisms. In CRYPTO, pages 469-480. Springer, 2008
C. Dwork. F. McSherry, K. Nissim, and Smith. Calibrating noise to sensitivity in private data analysis. In TCC, volume 3876, pages 265-284, 2006.
C. Dwork, F. McSherry, and K. Talwar. The price of privacy and the limits of Ip decoding. In STOC, pages 85 85-94. ACM, 2007. ISBN 978- 1-59593-631-8.
C. Dwork, A. Smith, T. Steinke, and J. Ullman. Exposed! a survey of attacks on private data. Annual Review of Statistics and Its Application (2017), 2017.
Erdos and A. Renyi On two problems of information theory. 1963. URL https://api Bemanticscholas www.oorr//ooooeeeeeeeo o 18080665
I. Haitner, N. Mazor, Silbak, and E. Tsfadia On the complexity of two-party differential privacy. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1392-1405. ACM, 2022.
Harary and R. A. Melter. On the metric dimension of a graph. Ars Combinatoria, 2:191-195, 1976.

---

A. Illanes and S. B. N. Jr. Hyperspaces: Fundamentals and Recent Advances, volume 216 of Monographs and Textbooks Pure and Applied Mathematics. Marcel Dekker, New York, 1999. Contains detailed development of compactness in hyperspaces.
J. Munkres. Topology. Featured Titles for Topology. Prentice Hall, Incorporated, 2000. ISBN 9780131816299.
C. D. Rodgers. Inverse Methods for Atmospheric Sounding: Theory and Practice. World Scientific Publishing Co., Singapore, 2000. ISBN 978-981-02-2740-1.
S. M. Seager. sequential locating game on graphs. Ars Combinatoria, 110:45-54, 2013. URL httpss//coobbnatooiaapppees httpp///tttrraapppssoooooorrraaa - a a-seueattial-ooctinn game-aa-eeeooo on graphs/
P. Slater. Leaves of trees. Congressus Numerantium, 14:549-559, 1975.
R. C. Tillquist, R. M. Frongillo, and M. Lladser. Getting the lay of land in discrete space:
A survey of metric dimension and its applications. SIAM Review, 65(4):919 2023. doi: 10.1137721M1409552.
S. Twomey. Introduction to the Mathematics of Inversion in Remote Sensing and Indirect Measure- ments. Elsevier, Amsterdam, 1977. ISBN 978-0444415880.
G. Ódor and P. Thiran. Sequential metric dimension for random graphs. Journal of Applied Probability, 58(4),909-951, 2021. doi: 10. 20.1..
12

---

We work in a metric space (X, x. The interaction lasts for a fixed number of rounds T, labeled t = 1,2,..., T. In round the reconstructor selects query point q e X. The responder then returns a real number r2 that represents a noisy distance from de to an as-yet-unspeciffed target, with A Related Work
We organize the discussion into two parts: research that focuses the responder's perspective, and research that centers on the reconstructor's 's perspective. In both cases, the relevant literature is vast, so we focus on works most closely related to the questions studied in this paper.
The Responder's Perspective. The reconstruction game is closely related to problems studied in privacy-preserving data analysis, where the goal is to answer queries on sensitive dataset while limiting what an adversary can infer (Dwork et al. [006). The foundational work of Dinur and Nissim [2003] initiated this line of research by showing that approximate answers to too many counting queries enable the reconstruction of a large fraction of the database. Their model uses counting queries on binary datasets, which are essentially equivalent Hamming distance queries on the Boolean cube {=1}". This connection is illustrated in Example
Subsequent works have sharpened and generalized this reconstruction viewpoint. Notably, Dwork et al. [2077] Dwork and Yekhanin (2008), and Haitner et al. [2022] provided refined attacks and bounds under weaker assumptions. More recently, [Balle al. 2022 and Cummings al. [2024] proposed
formal definitions reconstruction robusiness that relate privacy guarantees to the attacker's 's ability to reconstruct sensitive data. Recent work by Cohen et al. 2025 further explores the foundations
of reconstruction attacks, proposing new definitional
Resiliency- uncovering connections to Kolmogorov complexity and classical notions such as differential privacy.
Surveys such as Dwork et al. [017]] provide a comprehensive overview of privacy attacks and defenses, including reconstruction. We also note the classical work Erdos and Renyi [1963), which (in disguise) studies a version of the reconstruction problem on the Hamming cube in the noiseless setting.
The Reconstructor's Perspective. Our work primarily studies the problem from the perspective of the reconstructor, who seeks to locate hidden point using approximate distance queries. Related problems have been studied under several guises. A classic formulation is the metric dimension of graph [Harary and Melter 1976 Slater 1975 Tillquist et al., 2023), which asks for the smallest set of vertices such that all other vertices are uniquely identified by their distances to this set. This corresponds to an oblivious version of the reconstruction game, where the reconstructor must submit all queries in ad vancce.
A more sequential variant, closer to setting, is the sequential metric dimension (Seager 2013
Bensmail et al. 2020 Ódor and Thiran 2021], which measures the number of adaptive queries needed to identify an unknown point. These works mostly consider noiseless settings on finite graphs In contrast, our work allows noisy responses, considers general metric spaces, and studies the rate of convergence as a function of the number of queries.
The general formulation of locating a hidden point via distance queries has also appeared in applied contexts. For instance, the problem of reconstructing physical quantity from noisy measurements arises in remote sensing. including terrain mapping and atmospheric profiling. Classic references include Twomey [1977] and Rodgers] (200)). which formulate and analyze such problems as inverse problems under uncertainty. While much of this literature is algorithmic or statistical, our work provides a geometric and Barming-theorede view that complements these perspectives.
B General notation and basic facts
Let us remind the setup of the game and important concepts used throughout the proofs.
multiplicative parameter 2 0 and additive parameter 5 0.
Formally, the reply must satisfy
dist x (x, q)) S (1 + e)r; + 8, S (1+ +1+ c)distxx x (z. q:) +
13

---

to at least one point E X. In other words, after each answer the set
(( = x xEXi for all sist: dist distx S (1 c)r; + 6.1
S (1 + e)distx (2,
guaranteed to be non-empty. This set for the round called the feasible region. In the end the game the reconstructor outputs guess point fr, and then the responder commits to target point, choosing any x² E Ør.
The aim of the reconstructor is to minimize the distance distx(x" , ,rT), and of the responder is to maximize it.
Let us denote the set of all reconstructors which play game for I rounds by RCr, and the set of responders by RSPr. The final guess of the reconstructor R RCT we will denote by & and the output secret point of the responder A E RSPr by z'x. As recalled in Equation the optimal error must be
OPTx = inf sup sup distx (Tr, HC RSP w
Claim 13 (Monotone error in T). The function T + OP,x is non-increasing.
Proof of Claim 13 We show that for every T' 2 0, the function T + ( is non- increasing: that is,
OP + 8) OPTx
Fix any > O. By the definition of OPT (T, e, 6). there exists reconstructor R. that, after T queries, guarantees an error at most OPTx 6) + a against any responder.
reconstructor R' for T rounds, which simulates R for the first T queries, and then issues an arbitrary "dummy" query at round T + 1, ignores the response, and simply outputs the same guess f žτ that R would have produced after T rounds.
Now consider
Since the feasible region after T + queries is always contained the feasible region after T queries, and since the final guess remains the same, the reconstruction error of R' is at most OPT OT, 6) for any responder.
As this holds for every >> 0, it follows that
OPTx + 5 (PTx(T,e)))
required.
C Proof of Theorem 2
In this section, we present the full proof of Theorem The proof is based on geometric notions such the Chebyshev radius and the diameter of set, together with fundamental invariant of metric space: the maximal radius of an enclosing ball over all subsets of bounded diameter.
We begin by recalling the relevant definitions. For subset S C X, the Chebyshev radius of S, denoted r(S), and the diameter of S, denoted diam S, are defined by
r(S) inf sup dist (z,g), g), qeX zes
diam S = sup dist (x,
z.yES
The supremum and infimum of a set of real numbers A C TR serve the same purpose as the maximum and minimum. The key difference that the supremum or infimum may not be attained by any element of A. In such cases, one can approximate it by sequence {a; HeN A satisfying
lim a; sup A or 1000
lim a; = inf 2
important invariant used in the proof intitiituili the maximal radius of an enclosing ball among all subsets of X with diameter at most a-iss formally defined by
e ex(a) :=
sup
r(S).
SCX
(iam
14

---

In some cases, this supremum is attained; when that happens, we refer to the corresponding subset attained, we may consider sequence
S X as extremal. In general. even when the supremum of subsets (Sm meN of bounded diameter, diam Sm S a, whose Chebyshev radii converge to the supremum:
lim r(Sm) = ex
The statement of Theorem Srrcem@@onme consists of two parts: an exact (tight) expression for OPT terms of the function ex, and upper and lower bounds ex.
We begin with the proof of the first part.
Theorem 2 (First part). Let X be totally bounded metric space. Then, for any e, 6 2 0.
OPTx(c,6) = ex e e)6).
Proof. To prove the equality, need establish both directions:
X 8) 2 e ((2 + +))) and OPTx(e, S ex ((2 + e)6)
Lower bound. To show that the optimal error is at least ex (e)+)) it suffices to construct responder strategies that guarantee a reconstruction error arbitrarily close to this value.
Although the supremum in the definition of may not be attained by any single set, we can approximate it by a sequence sets (5m) with diam Sn, S (2 + +)6 and r(Sm) - ex ((2 + (e)+)) For each such set, we define responder strategy that preserves Sm. inside the feasible region, thereby ensuring that the reconstructor cannot achieve error smaller than r(Sm). Taking the limit yields the desired lower bound.
Upper bound. To establish that the optimal error does not exceed ex ((2 + e)0), we construct sequence of reconstruction strategies, each using query set of size Tw, such that the corresponding error remains within ex ((2 + c)6) + an, where an 0.
Since X is totally bounded, for any precision level a > 0, there exists a finite set Ta C X that forms an a-cover of the space. After querying every point in such cover, feasible region has diameter smaller than (2 + e)5 + ((1 + )² + 1) a. and hence
OPT(T c, 6) I ex ((2 + c)8 + ((1 + +c² +1) a).
The remaining step is to show that the function ex roght-continnous, i.c.,
ex((2 + c)8 + +a))
a'=0 ex ((2 - <))),
endowing the collection of compact subsets of X with natural metric that measures how far these subsets are from each other within X. This part of the proof is deferred to Appendix F.
which requires general machinery from
C.1 Lower bound via extremal sets
As mentioned earlier, the supremum
ex ((2 ( c))) c)
sup SCX (5))(5)
r(S)
plays the role of a maximum, although it may not actually be attained. In such cases, we simulate extremal sets-that is, sets that would attain this maximum- by considering approximately extremal sets: a sequence (5m) mEN satisfying
r(Sm)
ex (a),
diam Sn S (2 12+0 c)5.
m0000
For any E N, define responder strategy that, given any query X, replies with rg = (1 c) inf distx (g. + 8. SESm
Here, the infimum plays the role minimum; so if the minimum attained some point E Sm, this strategy effectively places B on the boundary of the feasible region (see Figure
15

---

Let us elaborate. We will show that for any point s E Sm. the response satisfies
F4 - (1 + e)distx x (g, 8) + 6,
and then, using the triangle inequality, we will obtain the reverse bound,
Fg 2 (1 + c)distx (g, 6.
The inequality Ta & (1 + diisttxxxx (edddiss(xx x (z. 8) + 5 follows directly from the definition of the infimum, which represents the minimal possible distance:
(1 e)distx x (g. s) + (1 e) inf distx (g, rg. zE8m
For the reverse direction, express inf ynf sesm dist (q. y) in terms of rg.
Tg -
inf distx (q. v) 1 1+c
y.
By the triangle inequality, for any two points y, 8 Sm. have distx g) distx (v.9) distx Since distx(s, & diam Sm s (2 + c)ō, follows that
dist (s. g) < distx x (y,, q) + (2 + e)o.
Combining this with the inequality (1 +1+ dis (v, 9) 2 dist x (y. q), and taking the infimum over E Sm, we obtain that for any point E Sm,
(1 + r)r + 5 = (1 + c)² inf dist v) + (2 + c) 2 distx q)-
yESm
Therefore, rg =.6 dist q) for every point s Sm, and hence the entire set S,, lies within the feasible region. Once the reconstructor selects guess point é, the responder may choose any point from the feasible region, and particular any s E Sm.
By the definition of the Chebyshev radius,
r(Sm) S sup distx("",a)) .),
x ESm
so for any a > O. the responder can choose point x² E Sm such that dist x²) > r(Sm) It follows that
OPT(T,,, 2 r(Sm). and r(Sm) -
Therefore,
C.2 Upper bound via a-covers
To show that the optimal error is at most ex((2 + c))), it suffices to construct sequence of reconstructor strategics, each using Tn queries, that guarantee reconstruction error of at most ex E) + an where 0; + 0.
Since the space X totally bounded, for any > 0 there exists finite a-cover Ta C X, consisting of T. points.
Take sequence of a, -nets with 0,, 0, and denote the number of queries in the corresponding nets by T, == |T..| Since is totally bounded, these finite nets exist.
Denote the points of the o.,net by (ueeee]..) and the responses of the responder by (rehtejr.) We claim that
diam &e (1g,, he(r)) < (2 e)ō ((1 + e)2 1)a. To see this, take any two points A, B in the feasible region after the interaction.
16

---

There exists query E fretrerry such that distx (A,g) q) I an- this query. Since A E ( r) and distx (g. A) S a2z, we have
Let r be the responder's answer to
r (1 + c)a, +
On the other hand, since B E r). we have
dist (g. B) - (1+ chr +8 +o
+2 c).
By the triangle inequality,
distx (A, B) & distx (4, B) + distx (A,1) S ((1 +6)² + 1)0n + (2 c)6.
Hence diam ((1,, re(.)))) < (2 + c) ((1 e)² 1)
Denote by a,, the quantity
1. The Chebyshev radius of Φ ((((g, (())(Tr) is therefore
bounded by ex ((2 + c)6 + d,,,, and hence
OPTx(Tn; ex ((2 e)0 a',))
By the right-continuity of x (see Appendix F.1 for every sequence of nonnegative numbers a', we have
ex (( + <) + d(n) - ex (x( ( c))) Therefore, we conclude the desired bound
( S ex ((2 +c))).
The proof of the second part of the theorem relies general properties of the function ex that hold for arbitrary metric spaces.
Theorem ( (Second part). If the distance (2 + e86 is realized a totally bounded metric space X, Le., there exist pair of points at this distance, then
(2 + = OPTx(c, & (2+
Proof. By the first part of Theorem 2 which we proved earlier,
OPTx(c, = ex ((2+c)0)
So suffices to prove that
1 (2 (++e)8 e)8 ex ((2 + +))) < (2 e)6
2
To show the lower bound e ((2 + c)5) 2 (2 + c)ō, it suffices to construct a set 5 S X of diameter most (2 e)6 such that every enclosing ball of S must have radius least 1 (2 + e)o. Indeed, by assumption, there exist two points 1/1, y2 X such that
distx (1 V2) (2 22+00 e)6.
Then for any point a E X, the triangle inequality implies
distx (11, x) dist (zx, v2) 2 e2
of the two distances must be at least [ +)55. Therefore, point in X lies distance less than 1 (2 + c)ō from both y1 and y2. and thus any ball containing both points must have radius at least this value. To show the upper bound e ((2 c)5) < (2 + c)6, it suffices to find an enclosing ball of radius (2 + e) for any set C X of diameter at most (2 + e).. Indeed, let
S be any point of the set, and consider the ball of radius (2 + e)8 centered at Since the diameter of S is most (2 + e),, every point y E satisfies dist x (æ, y) S dian(S) S (2 + c)o, so entirely contained in this ball. This proves the claim.
17

---

D Feasible-region calculus
The goal of this section is determine when there exists an answer R+ such that a given set S C X is contained in the feasible region (gg,r) r) (see Equation 2 resulting from a query at point
We will answer this question and provide criterion for such an answer in Lemma 12 For any set C X, define its a-neighborhood by
S. = U
268
where Bex, a) denotes the ball of radius centered at x.
We will also be interested in the following optimization problem: what is the largest value of such that the a-neighborhood of a fixed set C can be entirely contained in the feasible region for some answer to the query q? We will describe this quantity for convex Euclidean subspaces and specify the answer that the responder must give in order to preserve this neighhorhood within the feasible region.
To answer the first question, is useful to consider two natural candidates for the answer:
pin (S) == supses dist (s. q) q
max (S) == (1+ + e) inf dist (s, q) + T
1 +
sES
Intuitively, l p (S) places the farthest point of on the outer boundary of the feasible region while keeping all inside it, and mmax (S) places the nearest point of on the inner boundary while still preserving inclusion (see Fig. Fig. 4p.
Supremum and infimum of the set of numbers fdist (y. >>s play the same role as min distx (s, q) and max,es (s. The only difference is that sometimes the minimum or maximum is not attained by any point the set S. In such cases, one must take a sequence points {zx)ien C S that plays the role of the minimum or maximum, in the sense that
lim distx (y, 2;) = sup (y, s) or t0000
lim dist (v, = inf dist (v. s).
sES
sES
Lemma 12 (Consistency window). Fix set S C X. For given query q. there exists answer such that S is contained in the feasible region ((g.r) r) if and only if r rim (S) I mm Moreover,
this inclusion holds if and only if r E [n rq max (S) R
Proof. Assume the responder gives an answer r such that c rq. By the definition of the supremum, if
supzes distx(x,g) 0
1+6
then there exists a point A E S such that
dist (A.g)
146
and hence 2(g, r), contradicting the assumption.
Similarly, if > 7 max (S) = (1 (e) inf dist (s, q) + 8, then there exists a point B E such that
(1 c)dist x (B.q) 5,
and therefore B & ((g,r) r).
Hence, for any outside the interval (.min(()) r max (S)), there exists a point in S that lies outside @ (g. r). This shows that if S C ((g. r), then necessarily (rani max (S)], and in particular miii (S) < (S).
'Nte that we do not require the answer to be positive; may be negative, yet the feasible region can still be non-empty.
18

---

To prove the converse, suppose E (ramn( p r))] Take any point s E S. We must verify the two inequalities:
distx(8, - c)r + and s (1 c)ditttxsxxxxooo 8.
Indeed, since
r S max (5) (1+ +c) inf distx (z, 9) + (1 c)distx (s, + 66, ZE8
and
2 4 min (S) suP=es distx (2, 9) 8 distx (8. -
1 1+6
++6
we have E r). Since s E S was arbitrary, it follows that c f(g.r), completing the proof.
The observation above does not rely on any structural properties of the metric space; in particular, it holds even if the triangle inequality of set that may remain feasible after query, we need to use some form of continuity in the space. That's why, from this point on, we assume that the metric space is convex subset of R".
satisfied. However, to determine the largest neighborhood
Observation 13. Let S X, and let O. Suppose that for every S, the Euclidean ball B(x, oi) C Rn is entirely contained in X. Then:
Fy miin = +
max (Sa) -max {6, ( a(1 + +c)
1+c
Proof. We start by analyzing the supremum. We want to show:
sup dist (4. y) = sup dist x (s.9) 9) + a.
yES.
se$
The inequality
sup dist (q. 9) S sup dist x (s, q) veS.
#ES
immediate from the triangle inequality. Indeed, for any point E Sa, there exists some s E S such that y a)) Then:
dist distx (q. s) + dist (8, S dist (s, g) + a.
sE$
and so the inequality holds for all E S.. yielding the upper bound on the supremum. For the reverse inequality, take sequence (ai)ien such that:
lim distx (Ii, sup dist x (s.
#EB
For each x,, choose point y4 E B(x, a) lying along the ray from g through x; such that:
dist (g, y1) distx x4)
This is possible because the balls are Euclidean. Then:
sup dist x (q. y) 2 lim dist (g. = sup (xssxxxx,0) (8, - a,
yES.
1-900
SES
proving the desired equality. Now we the infimum:
inf dist (g. v) = max { 0, inf dist yES.
x (s. a) =).
.E
First, by the triangle inequality again, have: dist (g, v) 2 distx (g. dist (w,xx( (v. 2 inf dist (s,
19

---

for all y E Sa. Also, clearly distx (q. v) 2 0. Therefore,
inf dist x (g. v) 2 max {o.ing inf distx (8,9) a) yESa
sEB
To show the reverse inequality, consider sequence failien C S such that:
lim dist (zi, q) inf distx (8,
#ES
If ans ds,tx(s,9) < a, then for some Tj, we have dist (zy, 9) < a, so E B(z,, a) C Sa. and thus:
inf distx (q. =0 yES
Otherwise, all x; satisfy distxx (Iaa, 9) 2 In that case, for each æ. there exists a point ye E [g, æ.] such that distx (I,, y4) = a, i.c. y1 lies along the segment from to 2ú, at distance a from Ty. Then:
distx (ys, q) = dist (2 ①)
and so:
inf distx (q. S lim dist (g/, 9) inf dist x (s, 9) yeSa
1-000
sEB
This completes the proof.
Let us denote
Puinn (S) = inf distx (q. s),
Paaxx (S) == sup dist, (q, s).
=ES
aES
These quantities represent the minimal and maximal distances from the query point q the set S, and will be used to simplify the expressions that follow.
Lemma 14. Fix set S X and query point X. Define
( y (S)
Assume that a" > O. and that for every point Rf", contained in X: that is, B(s, a²) S X.
S. the Euclidean ball B(s, a²), viewed as subset
Then there exists an answer such that S.r C r). In particular, for the specific choice
(T) (1 (P (lhax) c6
1 1 c)2
we have Sar C (())
Proof. By Lemma
12
it suffices to verify that
min (Sax) I rr) S rr yaxx (S,
First, observe that
m.mxx (S) -
P = (1 + e) (S) + 6,
1
and therefore
+ (1 +1+ 2-
(8)
(1+6)²
20

---

To verify the lower bound, note that by Observation
13
4
(Sa.) = r. min (5) +
1 +E
maa (S) min (S)
min (S)
(1 + +1+=2=
(1 (1+c)² min (S) + r (S)
6)
= -s).
For the upper bound, we distinguish between two cases depending on whether Pinjo 2 a* or Puii a'. Indeed, the form of r (Sa-) ) is case-dependent, with two distinct formulas: Pmin 2 a², then (Sa.)(an)) - - (5) - (1 e)a" otherwise, rg (Sa.) = 8.
Case Phnin 2 a². Then by Observation 13
1q y (Sax)
r4 max (S) (1 + t)aa
(1 + e)² c)² (T (S) 1 (5))
r (S)
+ 6)2
(1+c)2 (ila(()) + 1 (max(())
(1 + e) +1
(S).
Case Puin <², In this case, we observe that
1 max (S) (1 +)) e) p + (1 + e)a" + +
and therefore
8 >>1 r max (S) - e)e = (S),
again (5) < 5 = r.max (S.. required.
This completes the proof.
For later use, we express the quantity a* in terms of Pini and plaxx since this representation will be useful below:
(1 + p2 pm
-aax + (2 e)6
(1+6)²+1
This leads to the following observation.
Remark 15, Assume that diam < (2 e)6. Then the radius a* of the neighborhood Sar, as defined in Lemma 14 can be decomposed into two nonnegative terms, a* = 01 + 02, where
(2+ (supnes dist (z, 9) inf (x.
01
e)+ +1
and
(1 (1+c)--1 inf dist x (I, q). zes
a2 = (1+ +1
Note that on 0. since supzes distxx(x,0) infzes dist 9) diamS < (2+
Observation 16. Assume and fix the regular simplex C X with edges of length 28, and the query E _ Denote
A = =argmax, A. dist (A, 4).
B = argmin A.EA dist (A,iixA(A,0 (A,
Then Lemma 14 can be simplified; the a² neeighhooooood lies in the feasible region: D.. C (gg, r. (A)) for
r (A) distx (q, A) + dist (g, B)
2
a* dist (g, A)
dist (q, B)
2
21

---

Lemma 17. Assume we are in the c = 0 game scenario. Fix ő > O, and let A = A ... An be a regular simplex with edges of length 28. For given point 9, ler A A be the farthest vertex from 4, and let B E A be the nearest vertex (in the case of ties, choose any).
cos ZBAq S 51- 11- a 8'
then
ri( 9 7A+00 +
Da C ((larr
2
Proof. It suffices to show that BAA, a:) and B(B, a:) are both contained in & ( (gg.17 (A)). Let us estimate Aq Bq. We will show that
Aq Bq S cos LBAq. 26. 22.
Drop a perpendicular from y onto the line AB, and let the foot of this perpendicular be H. Denote the angle ZqAH by o and the angle L by vb
0
A
B
H
A
H
B
(a) Visualization case
(b) Visualization case 2
Figure 5: Visualization of two cases
We distinguish two cases: H & AB and H E AB (see Figure 5) Note that in both cases,
π
0 <<<
and since the cosine function decreases on this interval, we have cos Φ 2 cos vp 2 0.
Case 1: H & AB. Since Aq² compute:
9H2 H and Bq² 2H² HB² and AH BH 28
Aq² By²
AH BH²
AH BH
Aq
Bq
28
Aq + Bq
Ag + Bq
Aq + Bq
On the other hand since cos á 2 cos 1h:
AH + BH
Aq cos Φ + Bq - cos 1/
S 1.
Ag + Bq
Ag + Bq
Hence
Aq - Bq S 25 cos 25 cos LqAB.
Case 2: Hl AB. Similarly since AHl BH 26:
Aq² Ba²
AH2 BH²
AH BH
Aq Bg
28
Aq Bq
Ag + Bq
Aq + Bq
25 Aq cos Φ
Bq COS 1/
Ag Bq
which again implies
Aq Bq < 28 cos é 28 cos LgAB.
Now take a point MA E B(A, a). By Lemma assumption a S 5(1 cos BAq), hence
MMa S aA+a S qA+ 5(1 cos LBAg) < 9A Aq Bg
+ -rī(A)
22

---

Also, because a < 6, it follows that M,4 2 (4) Hence MA E ((g.rz
similar argument applies to any MB E a)) Indeed,
qM 2 qB - a 2 qB 8(1 cos <BAg) 2 r2( 5,
and again < 8 implies MB E $ (A)). Thus B(A, and BBB, lie in ((g,rg(A) completing the proof.
E Proof of Theorem 6
Theorem (Theorem 6 Restatement). Let X C. R" be a bounded convex set equipped with the Euclidean metric such that dim X > O, and let 2 0. Then, for all sufficiently small 8 >> 0, the space X not (c, 8) (-so-----ofiiiii except the case where c and dim X =.
Proof. Since the reconstruction game is played entirely within the space X the sense that all queries, the final guess, and the secret point lie X-we we may assume without loss of generality that X CR, where n dim(X) k) is the affine dimension of X.
We begin with the special and simple case where 0 and dim with endpoints a, b; without loss of generality, we assume that both a, b E X. (The cases where X is half-open or open can be handled similarly.) If 2 (b - a2/2. then the optimal error equals the diameter of the space, and the reconstructor can trivially achieve it by outputting any point in X without submitting any queries. Otherwise, d < (b- - a2/ the reconstructor submits a single query at one of the endpoints, say qı a, and receives r1). The feasible region then becomes interval of length at most 26, and by guessing its midpoint, the reconstructor achieves the optimal approximation error of 6.
In this case, X is an interval
The remaining cases- either > or dim X 2- are more challenging and constitute the core of the proof. We divide the proof into two cases: one where 0, and one where >> 0. In both cases, the proof follows a similar strategy. We show that for all sufficiently small 5 0, there exists a responder strategy that guarantees, for every number of rounds T, that the feasible region contains an extremal simplex År whose Chebyshev radius is strictly greater than the optimal value OPT(e, 8). This suffices to prove that the optimal error cannot be attained in finite time.
More precisely, we show that for each 0, 1..... T, the responder can ensure that the feasible region contains an og-neigbborhood of regular simplex A, of diameter exactly (2 + c)o, where the neighborhood is defined as the union of all balls of radius a, centered at the vertices of A, Since
such a neighborhood contains a regular simplex of diameter (2 + t) + V [2(++1] Or. it follows that the Chebyshev radius of the feasible region is strietly greater than OPT(c, which corresponds to the Chebyshev radius of a regular simplex of diameter (2 + c)5.
The proof proceeds inductively. We assume that after t rounds. the feasible region contains an O₂- neighborhood of a regular simplex A, of diameter (2++)ō, and we show that for any query 9t+1 E X, there exists response such that the updated feasible region contains an 0++ neeighboooooo of some (possibly different) regular simplex A441 of the same diameter. Moreover, 0++1 = fe,a(0r), where the function fe, is defined by:
a
c= 0, O2 <> 0.
fa,
2818: (1+c)=
2(1+e
Thus, the responder can recursively maintain an a--ncighborhood of a regular simplex throughout the game, where a; = _! (ag). and og is the maximum value such that X contains an negneighborhhood of a regular simplex of diameter (2 + e)8. This completes the high-level argument. To complete the inductive proof, it remains to establish the base case and then develop the tools needed for the inductive step.
Base Case. Since X is a bounded convex subset of I with nonempty interior, it follows that for any >> 0, there exists sufficiently small > 0 and some on such that X contains an neihhbbbboddoo of regular simplex A with diameter (2 + e)o. This establishes the base case for
23

---

our induction: at round t = 0, the feasible region contains a neighborhood 4 S X that satisfies the required conditions.
Inductive Step. The remainder of the proof develops the geometric tools needed to carry out the inductive step, namely to show that such neighborhood can be maintained (with decreasing radius) after each query. We now introduce the some notation used throughout the argument.
Notation 18. Let O < S 6, and ler A = {Ao,A1:... A1...., A.) y be a regular simplex in IR" of diameter (2 + c)o. We define the a-neighborhood of A, denoted Das as the union of closed Euclidean balls of radius a centered at the vertices of A.
A query point E Rn is called good (with respect to A and (:) if there exists response such that the entire neighborhood Da is contained in the feasible region $(g, r); otherwise, q is called bad.
We will use the special response r rद (A) defined in Lemma 14 to ensure that the neighbor- hood Dow. remains feasible; this choice will be sufficient for our mauctivve argument.
E.1
Case > 0 (translation strategy)
Assume the responder receives the query and has far managed to keep the a-neighborhood of a regular simplex C RR,, with edge length (2 + c)ō, inside the feasible region. Without loss of generality, may assume that 4a (2 + c)6.
In this subsection, we will show that when > 0, there exists another regular simplex A' with the same edge length such that
A c (A))) where a' (1 + +[}+ -1
A C Das
2(1 + e)²
This will be sufficient to establish the induction step for the case > 0.
In the terminology of Notation 18 the query point y may be either good or bad with respect to the simplex A and neighborhood a' If is good, we are done by simply taking A' := A.
If the point is bad, we will use the decomposition of the neighborhood sustained by the an- swer r (A), as described in Remark 1.5 in order to construct new simplex.
Let us remind the reader that, by Lemma 15| there is a formula for the radius a* of the neighbor- hood A which corresponds to the feasible region after answering with r (A). Remark 15 states that this radius can be decomposed into two nonnegative terms.
In the case 0, the second term will be of particular interest:
(1 + e)² -1 inf dist distx(x, (1 e)2 ZEA
a² a1 + a2
02
Since assumed that the query g is bad with respect to the simplex A and neighborhood a', it follows that
(1+ (1+c)-1 inf dist (z,
(1+ +1 aEA
In particular, this implies
(1 e1+ +1
(1 (1+ +1
dist (B,9)= < a'.
a a',
(1 + +)
2(1 + +)²
where B = arg minggeg dist (x,g) is the closest vertex of A to the query point g.
Define the shifted simplex A' A ग. where the vector is in the same direction the vector gB, and its length is
(1 (1+e)=-1 a' a'== (1+ a'
c)
1 = a
(1+6)2
In the degenerate case when q B, choose any vector ग of that length.
24

---

The shifted neighborhood satisfies D C Da. Assume E A'y; then there exists a shifted vertex A' := A + ö (that is, A' is the image of A under translation by the vector o¹) such that [AA', a').
Let us denote by B' the point obtained by shifting the vertex B of (the one closest to ①) by the vectir ह.
We claim that B' is the nearest vertex of the translated simplex A to the query point q. This follows from the triangle inequality and the bounds
dist x (B,g)= S aa- a', a < (2 + e)
4
Indeed, consider any other vertex C' = =C A' where C * B. Then:
distx (g, C*) 2 distx (g, C) || dist (q: C) (a a')
On the other hand, we have
dist x (g, о) 2 distx - xist (g. B) 2 c)6 - (a d'). Combining these inequalities gives
distx C*) 2 (2 + e)o 2(a ad).
Meanwhile, the distance from to B' satisfies
distx (g, B') I dist (g. B) + (a a²) S 2(a a').
Since we assumed a < (2+c)6 it follows that
distx (q. B²) < 2(a a') < (2 + e]6 2(a a') S distx (g. C²),
which confirms that B' is indeed the closest vertex of A' q.
Since B + 0' the vertex of the new simplex A' closest to g. we have
distx (4, B + 0) 2 | = (1 (1+c)* +1
(1+ oa
Therefore, by Remark 15 (which follows from Lemma 14), the entire neighborhood A/y is contained
in the feasible region:
A C & (A))).
This completes the argument.
E.2 Case e = 0 (rotation strategy)
The strategy for handling the case 0 will be similar. Assume the responder receives query q- and that the a-neigbboroood of a regular simplex A, with edge length 25, is contained in the feasible region. Without loss of generality we may assume that a < 3.
We will again show that there exists another regular simplex A' with the same edge length, such that
A/ C A.,
A c Φ ( where a' 81 28
In the 0, the agooo points those whose distances to the simplex A were sufficiently big. Obviously, when 5 = 0, this method of locating good points no longer works: for example, the entire line passing through two vertices A and of the simplex A consists of a-bad points for any a > 0.
Note also that in our earlier rggument-whert would become good with respect to the shifted simplex- we did not require a full characterization of bad points. It was enough to identify property shared by all bad points and then move the simplex so that the given point no longer satisfies that property.
moved the simplex so that previously bad point
The same strategy applies in the case 0, using Lemma 17 be the nearest vertex of A to the query point q, and let = arg max distx (g, A;) be the farthest.
Let B arg A, dist (g. A:)
25

---

By Lemmaa 17 if the point is bad, then the angle between the vectors AB and Aq that is, the angle ZqAB must be sufficiently small. Why is this the case?
Note that since B is closer to than A, the angle ZqAB lies in the interval [0, T/2). Over this interval, the cosine function decreases from O. Therefore, the point q a bad, we must have
a'
LBAq < arcoos (1- (1- 8
cOs AB, Ag
The regions consisting of points satisfying LBAq < arccos (1 (1- 4) illustrated in Figure
XXX
(a) Two-dimensional case
(b)
Three-dimensional case
Figure 6: All bad points lie in the orange region
The proof proceeds follows. We assume that the point y satisfies
LBAg arccos (1-3)
a'
Otherwise, by the argument above, the point is a' aoogoo, and we can provide the answer using Lemmal 17
We then construct isometry such that the transformed point q' := 7(4) no longer satisfies this property. That is, let A' and B' be the farthest and neares p vertices of A with respect to g'. Then the angle /B' A'q' satisfies
1 (1-3)
a'
LB'A'q' 2 arccos
8
Notice that it would be sufficient to construct such an isometry: if the point 7(4) is a'-good with respect to the simplex A, then the original point q is a'-good with respect to the transformed simplex A' : A':=7-((A) (A). Once such rotation is constructed, the remaining task is to argue that A C A...
Denote by 28 and b = 3 the normalized neighborhood radii.
The main challenge in constructing such an isometry is that, we are not careful- say, we transform
the space in way that ensures ZBAq' 2 arccos [ g the point q' may still turn out to be bad.
This can happen because the isometry might unintentionally change the identity of the farthest or nearest vertex of the simplex with respect to q'
We will even prove that the transformation preserves the identities of the nearest and farthest vertices.
26

---

This is why in Lemma 23 we constructed a small enough isometry Ree for the specific query such that it does not change the identity of the farthest or nearest vertex of the simplex with respect to [g)
Define 0 = arccos(1 26), and consider the rotation R2,, defined at the beginning of Appendix F.2 (see Equation 4). associated with the query q and the simplex A. Recall that this rotation acts on the plane span A, B3 Q)-where is the centroid of the remaining vertices in A \ {A, B3} by rotating around the point A through an angle of 28. On the orthogonal complement II it acts the identity: R28 I=- Idn.
Since we assumed that the point q is abbba,, we must have
LBAq < arccos (1 22b) = 8.
Notice also that, since we assumed a < .. it follows that a' 32.81
Therefore,
a'
cos
26
32 81
18
which ensures that 0 < H This inequality can be verified using standard analysis tools, such as Taylor expansions of the cosine function.
18.
Hence, we may apply Lemma 23 which states that the farthest and nearest vertices with respect to q' R2 are preserved under this isometry whenever @ S TB.
arg min distx (A;, B, A,EA
arg max dist x (A, A. A,A
Moreover, Lemma 23 also states that AB > simplex A.
0, and hence o' is a'-good with respect to the
The remaining task is to show that A C C..
The largest displacement under the rotation Red occurs in the plane ABQ. Since all vertices of the simplex, except for A, are equidistant from the origin A, the point is therefore the farthest from its image (B). Hence, to verify that A A.. it suffices to show that
B(B', C B(
Formally, this implication is proved in Lemma
To verify that B(B', a²) C B(B,a), a). we apply the Law of Cosines the triangle ABAR (B). where both sides dist x (A, B) and distx (A, R20 (B)) equal 26, and the angle at vertex A is 20. This gives:
dist (B, R20 (B)) = 482 + 482 852 cos (20) = 8 cos()
so
distx (2s
Ros (B)) 28 2(1 cos (20)).
Thus, we require:
a 2 28 122 2 cos(20)
4 a b 2 v 2( cos (20)).
Using the identity cos(20) 2 cos² 0- - = 2(1 - 2b) 1, we compute:
c20(20)
1 [2(1 - 26)² 1
sb(1 b).
Thus, the condition becomes:
- b 16b(1 - b).
Since a > we can safely square both sides:
(a
b)² 2 16b(1 - b)
+ 17b2 - (16 + 2a)6 + a² 2220 0.
The discriminant of the quadric polynomial f(b) 1762 (16 + 2a)6 + a² is
D
(8 + a)² 17a².
4
27

---

(8+a)+ / (840)2-170
Since <
the inequality - b 4vb 62 holds only when
17
0 0<bs (8+ v(8 + a)² 17a
17
Finally, note:
(8 + a)
((8 a)² 17a
a²
a² b
(8 (8+a) + v(8 + a)² 17a
which confirms the condition, completing the argument.
F
Technical Results
For completeness, we collect in this appendix several arguments deferred from the main text. We begin in Appendix F.1 with a topological result establishing the right-continuity of e (a) on totally bounded metric spaces. Appendix [22 we turn geometric techniques involving rotations of
regular simplices, which play an essential role in the proof of Theorem 6 Finally, in Appendix F3
we give detailed proofs the illustrative examples that were sketched Section 2
F.1 Right-Continuity of
We start by fixing notation. For a subset S in metric space (X, distx), the Chebyshev radius of S, denoted r(8), and the diameter of S, denoted diam S, are given by
r(S) inf sup distx (I.4), x wES
diam S sup dist (z, v).
a.yES
Recall that the number ex (a) intuitively the maximal radius of an enclosing ball over all with diameter at most a- and formally defined as
e ex(a) =
sup
r(S).
SCX SS
Our goal in this section is show that ex is right-continuous for every totally bounded metric space X.
Let (X,d) d) be metric space. Consider the set of compact subsets of the space X, denoted by KC(X.
Given two nonempty compact subsets A, B S X, their Hausdorff distance defined as
(Ast = max
sup inf dist (a, b). sup inf dist.x (a, (a, b)) a bEB
BEB aEA
Intuitively, this measures how far the sets are from being contained in each other's neighborhoods. The space (KC,), distx((x) known in the literature the hyperspace of X.
A classical result states that XC(X) is compact whenever X is compact (see Theorem 3.5 Illanes and Jr. [199)). Consequently, every sequence compact subsets admits subsequence that converges in the Hausdorff metric, which implies the right- right-continuity of e (a.). The proof is given below.
Lemma 19. Let X be a compact metric space. Then the function e (a) is right-contimuuus.
Proof. Observe that any subset S X has the same diameter and Chebyshev radius its closure. Hence, in the definition of x (a), it suffices to consider closed subsets, which are compact since X compact:
ex ((2 + +)0)
sup SC compact ((5+())
r(S).
Both the Chebyshev radius and the diameter are continuous functions on KC(X). Indeed, for any two compact A, B K((). |diam A diam B < disticix) B),
Ir(A) -r(B) < distx((x) B).
28

---

Now take any decreasing sequence Pn + B. Notice that the function ex (x) is non-decreasing, and hence the sequence e (8n) is non-increasing. To prove the result, we need to show that ex (3,, + (3))
Suppose, for contradiction, that there exists 7 > 0 such that for any natural numher N, ex (Pn)) > e xB) +
Then, for each natural number n, we can find Sn, of diameter at most S, such that
r r(S)) > ex (3) 2
Since ((()) is compact, there exists convergent subsequence of compacts subsets Sm(n) + S in the Hausdorff metric. Continuity of the diameter implies diam S S B, and continuity of the Chebyshev radius gives r(Sm(n) + r(S). Hence,
r(S) ex (3) + 2'
contradicting the definition of e This proves the claim.
Lemma 20. For totally bounded metric space X, the function ex is right-continuuss.
Proof. A standard extension of the Heine-Borel theorem states that metric space is compact if and only if is complete and totally bounded (see Munkres [Theoee 45. The completion X of a totally bounded space X is complete by construction and remains totally bounded, hence compact. Because X is dense in X, every subset of X can be approximated arbitrarily well by subsets of X (and versa,, so e g. Lemma 19 now applies to X, yielding the desired right-continuity for ex
F22 Geometric tools for Euclidean simplices
This section presents the geometric constructions that, while essential, would otherwise disrupt the logical flow of Theorem 6 in which they are applied.
Let A vertices, set
{A,7% be a regular simplex in R with edge length 25. To distinguish two specific
A
= A2.
Let Q denote the centroid of the remaining vertices:
Σ C. CEAHABB)
Consider the rotation
Roe 1R" + R
that fixes the vertex A, acts in the plane II = span { (A, B, rotation by angle 20 around A in the direction from AB AQ along the smaller angle between them, and acts as the identity on the orthogonal complement II=
If we place the point A at the origin and choose an orthonormal basis di..... d, such that span dg de) II, and
A = k di with lo > 0,
AQ kidj + k2dzz with Kr, K2 > 0,
then the rotation Ree represented in this basis by the matrix
cos cos(20) (20) sin 20)) 0
sin(20)
0
cos(20) 20)
0
1
0
Rze
J0We use to denote the discrete set n + vertices of regular simplex, rather its convex hull.
Notice that such basis exists because LBAQ < J.
29

---

The upper-left 2 acts the identity on II
2 block corresponds to a counterclockwise rotation in the plane II, and the rest
This transformation is a Euclidean isometry: it preserves all distances and acts as a rotation in the ABQ-plane while leaving the orthogonal directions unchanged.
NK for some points {N, M, K), we will often refer to cos ZMNK as cos(U,, v2). This emphasizes the computational role of the cosine as the inner product between the normalized vectors 01 and u2:
Remark 21. Given two vectors = NM and :=
1/1
12
CO8 <MNK
12
The following lemma is basic yet useful observation.
Lemma 22. Let II be plane, and let A, B E II be two distinct points. Fix any point q R", distinct from A, and let Hg denote the orthogonal projection of q onto II. Then,
< cosLgAB I cos2H,AB, Lf <
0 cos 2 cos2H,AB, Lg > 2 cos = cos =0, 0,
LgAB =
Proof. Since the cosine between vectors can be computed via their inner product (see Remark 21 the key observation is that
Aq AB AHl.:
because the vectors AB and Hºg orthogonal. Indeed, since Hg is the projection of q onto the plane 1I, the vector Hg9 is orthogonal to every vector in I1, including AB. Hence,
AB Ay AB AH,
Now, if Hg # A (the case Hg = A is trivial), we compute:
Ag
AB
AH, AB
cos( (Ag AB) = A|gl
|AB||
||Ag|l
ABy
||AH,
AH,
AB
||A
||AH,
|I
|AB
||AH,
cOS(AH, AB).
AAq
Since AHg is the projection of Aq onto the plane II, have
AAH gl
0
$ 1,
||Ag|
with equality only if q E II.
Now observe that for any angle S n
cos Φ < 0
2
Thus, the product cos( (AH, AB)
||A |l is: smaller than cos( LH,AB) <gAB n. 2' larger Agg
LqAB n and equal when the angle is z since then both cosines vanish. 2.
This completes the proof.
Lemma 23 (Rotation in the ABQ-plane keeps near/far order). Assume for query point E R the nearest and farthest points are B and A respectively; that is:
B argmin EA distx (g. Ai), A argmaxA.cadiste (g,
30

---

Then, for any angle 0 < whenever ZBAq S 0 the isometry R29 preserves both the nearest and 18 the farthest vertices of A with respect to q:
B = argmin A. dist (Rzaq, At),
A A distx (R20q, A.).
Moreover, the rotated point of == Reeq satisfies
AB >
Proof. We will show that the nearest point B remains the nearest, and that the farthest point A likewise remains the farthest, whenever ZqAB I x Finally, we will establish that < >> 6. 18
Our argument will be carried out in an explicit orthonormal basis adapted to the geometry of the simplex.
Coordinates an orthonormal basis.
To simplify the calculations, we first scale the simplex A Ant1 by factor of 1/(28). We then embed p=+1 by mapping the 1h vertex v2 ct Throughout, we == A1 and B A2. In these coordinates,
AB V2 (-1,,,,,, 0),
AQ
v2 1 (-1,0,
-
Next, we introduce the two unit vectors spanning the aftine plane ABQ, which will play key role in defining the rotation R2e (see Writing the plane as
ABQ A A (d1, dz),
with Minkowski addition and linear span, we take
di d=
de
11, -1, n-1
2(++1)
n-
direct check confirms that (di, da) is orthonormal. Moreover
2AQ AB
dz.
2AQ - x dg + d..
Completing the basis. Pick an orthonormal completion (d of (di, dzj. A convenient choice is
de = QAg
|[QAs]] 7 (0.0, a-2
a-1' n-
n-1 = 2-
and analogous definitions for 2 4.
With this basis, for any 3 S Σ n + we have
AA
2(n
d.
+
n de + di)
Coordinates the query point. Let q satisfy LqAB < 0 and write
Ag
Σ dy 1=1
so that
21
coos<qqA)) 2 cos 0.
(5)
EE
2
In particular, 21 2 (cos (/os0/sil sin 0) |=2|. Observe that for any vertex A; of the simplex and for any point C, one has
IACI > |A,C|
+ 2 AAC
AA, > 1,
(6)
since
|A,C IAC
AA 2
ACI12
2AC
AA, +1.
31

---

Moreover, for any point C with coordinates AC Ei=1 ii= Yod,, straightforward calculation shows that
2(n-2) AC AA; 1 (V 2-1 Vi
1/2 + y1
Step I: the farthhett point remains the farthest when ZqAB < g.
Because Reo acts as a planar rotation in (d1 d2) and fixes the orthogonal complement, we have
Aq = (cos 20 21 sin 20 22 ) + (cos 20 22 + sin 20 21 )d2 +
24 dz.
Fix any n + 21126 2 3. By Eq. and Eq.
to show that |Agl 2 |A implies |Aq' 2 |Agg'
suffices to verify that the inequality
2(n 2)
23
+ 21
72
implies
2(n-2) 2)
cos 20 sin 20 21) + (cos 20 -sin 20 22) 1.
For this implication to hold, it suffices verify
sin 20 20 1) 21 2 (V (1 cos 20) sin 20) 22.
or, equivalently (using the double-angle identities),
n++ cos 0 sin 0)
++ sin 0 + cos 0) 22.
Because 21 2 (cos // sin 0) |22| (see Eq. 5 is enough verify
cos sin
cos sin
sin + cos 0,
which in turn is equivalent
cos 20 sin 20 0.
The latter holds for every
completing the proof.
Step II: the nearest point remains the nearest when ZqAB S 18
We will prove that whenever LQ'AB AB S 6. all distances A for A, & {A, B) are greater than [Ba'). To that end, let denote the angle Za' AB AB by & and fix any n 12 12123
By Eq. (6). the claim is equivalent to the scalar product inequality
Aq' BA
Aq A.A,
and by Eq. 77) in our orthonormal coordinates, this becomes
Aq AB 21 2 1
((n n-1 24 +
n- 22 21
Aq' AA
or, equivalently,
21
2(n-2)
23 +
22.
(8)
n-1
Assume LB'AB= = 1 Then, by Eq.
5
COS ④
21 sin $
23 + 23
2
v3
23 2
where the last inequality uses
cos d sin
cos( sin(x/0)
/3, which holds for all 0 < < 7/6.
32

---

We will now prove that
(
322 + +2² 2
2s +
n-I 22
n+1
Expanding the right-hand side, this is equivalent to
+ 1 2(n -0-)) 2) 22 2 21
2(n (n (n - 112
2422:
71 which is always true by the inequality U2 + 52
S,S applied with
+ n
2(n 2)
2
S s V
22
11
Putting these estimates together, we obtain
21 2
2(n-2) 323 327 2
24 +
n+1
22
n-1
which is exactly (8) Hence BByl S |4,' whenever <q'AB π
Consequence for the rotated point. If the rotation parameter satisfies 0 < π 1/18, 18, then the rotated point obeys ZB Ag' S </66; therefore the point B remains the nearest after rotation.
Hence, if the angle < I the angle /BAd < It and the point B still remains the nearest. 18
6
Step III: proving <9 AB 0
remains to verify that the rotation R20 sufficiently increases the angle, i.e., that LBAq' 2 A.
To show that decompose the vector Ag as
Agg AH Hqg.
where Hg is the projection of y onto the plane IT. Denote R29 HH,) by H Since Rza is not only an isometry, but by construction also linear transformation with placing the point A as the origin:
Aq
R20 Aq]
R2 [AH,]
g
R20 H
AH q + Reel Hg4
Since the rotation R29 preserves the vectors orthogonal to II, it also preserves Hzq. Hence (see Fig. 7
Ay' AH + Hgg and moreover, H is the projection of q' onto the plane II.
To see that Lg' AB 2 6, note that the cosine function is decreasing on the interval [0, m). Therefore, it suffices to show that
cos( Lg' AB) S cos 0.
For this purpose, will use Lemma 22 which formalizes the observation that projecting a point onto a plane either increases or decreases the cosine of an angle, depending on whether the angle is acute obtuse. Specifically, if AqAB J.J then cos LqAB > cos / HH, AB, and the inequality reversed when the angle is obtuse However, to apply this lemma correctly, one must verify that either the original angle or its projection is acute or obtuse, as the conclusion depends on this distinction.
By Lemma 22 we have cos ZH, 2 cos LqAB, since /qAB < < I. Therefore, using again that cosine decreasing the interval [0, n). follows that /H, 0.
It also shows that the projected angle acute obtuse if and only if the original angle obtuse.
33

---

1T
11
Hq
Figure 7: Rotation and vector decomposition of Aq.
Using the triangle inequality for angles, and the fact that /H₃ = 20, we deduce:
LI, & AH, LH - 20
30 <
ZH 2 2 AH, ZH, H 2 20
Therefore, applying Lemma once again, conclude:
cos <g AB S cos ZH, & cos
Lemma 24. Suppose d', a are such that Rig BB(B,o') B(B,a). Then
R5d A.r C..
Proof. Denote the simplex R2d A by A' To ensure the inclusion A C A.. it suffices check that vertex of the simplex moves by than a' under the rotation Rz0-
Let C be any vertex distinet from A and B. Then the point C does lie in the affine plane ABQ
Denote by B' = R20 B, by C' == R2 and by Q' = R2aQ. The point C' is projected onto Q 13 Then,
AQ AQ
cos (Q, AQ')
cos 20,
|
due to the construction of the rotation. On the other hand, since AQ 1 QČ, one has:
AQ AQ' + |CQI2 ||Q]] 2 CQI22
AQ -AQ'' cos 20,
cos AC, AC')
||QQI
since adding the same positive value to both the numerator and denominator of ratio in (0, 1] does not decrease the ratio. Now,
|BB' -
|AB |||B AB 2 -AC
= =2 (AC. AC -AB-AN
2/| ABI2 (cos(AC,, AC - cos 20) > 0,
which shows that indeed ||CC|| < |B'|||
But this fact is not essential; the argument still holds without requiring that the projection coincides with Q.
34

---

F.3 Examples
We begin by analyzing the game on the real line.
Example (Example from the Introduction). Let E > and ő 2 0. Then, for any number of queries,
(PT = to0.
Proof. The idea of the proof is straightforward: since the space is unbounded, the responder all-ad in the first round-return an arbitrarily large answer. This ensures that the initial feasible region is large as desired. Then, over the course of T interactions, the responder can control how fast the region shrinks, ensuring that the final feasible region remains arbitrarily large.
Let us elaborate.
At the start of the game, for any large number Lo > 0 and any query I. the responder may answer with
1+c rg = (1+))2-1 (Lo c)))
which results a feasible region that includes two intervals length Lo-
Now fix an interval [a, b] of length I, and suppose the reconstructor asks a query E R. The responder then answers with
max b). al}
1
This response places the point in [a, b) that is farthest from q right on the boundary of the feasible
region (gg, r,). In particular, this implies that every point x: E [a, bj satisfies |x gl S (1 + c)r, +
Assume without loss of generality that max{lq b), l al} l9 b/, i... q S atd On the other hand, all points r E [a, b] satisfying
b gl - (2+
(1 11+6 c)2
also satisfy (1 e). -1 + +822 T.. Thus, all such points lie within ((g,
The length the subinterval of (a, b) consisting of such points
((1 c)² - b 9l + (2 + c)6 ((1 + e)² 1) (1 c)
((1 [1)+c)-11 al-
2(1 + c)2
2(1 + c)
Hence, on each round, the responder can reduce the feasible region's 's length by a constant multiplica- tive factor e rounds can still have length at least cT Lo. which diverges as Lo - co.
(1++)*=1
2(1+e)7 Starting from interval arbitrary length Lo, the feasible region after T
Therefore,
OPT +00.
The next example demonstrates that when 0, the real line is -cseddooe fonitt for every 5 > 0:
Example 25 (Pseudo-finicee finiteness on the real line). For every 8 2 0, the real line IR with its usual metric (0, 5) --pseudo-fiiite.
Proof. The optimal reconstructor strategy is to ask two query points qı, 92 E R with 42 - 91 > 25. Let the answers of the responder be 7', 1'2.
Intuitively, each answer restricts the secret to intervals of length 28 centered at y Er. Because the distance between the center of the leftmost interval and the center of the rightmost interval exceeds 28, most two of the four candidate intervals overlap, and their intersection has diameter 28, attaining the optimal error (see Figure
35

---

Formally, the feasible regions are
(q T1) = B (q: - -r1 U (q) + +r,,) + (42 12) B (92 -002) UB (02 + 02,
Assume there are two points in the intersection (11, 11) n ((12. such that x > 26. These points cannot in the same ball radius 6, hence
x E B (11 r1,8),
y E B (q1 r),
and also
x E (02 - 82, y E B (g2 + r2, 6).
Therefore, the balls with larger and smaller centers must overlap:
q2 + 72 (g) + rz)l < 28, and
192 - - (9) - r1)l < 26.
On the other hand,
1/2 Q1 + 12 rı
1/2 21 + r2 2 2/02 21 > 46,
which leads to contradiction. Hence the result.
feasible
T2
T2
F1
221
23
Figure 8: With 191 - 92l > 26, only the red interval [a] + ri - 8, + + 6] and the blue interval r2 + 8] intersect, pinning the secret point to their (purple) overlap.
Ig2 12
6, O2
The following simple observation shows that in bounded metric spaces, the reconstruction game becomes trivial whenever (2 + e)ō exceeds the diameter of the space.
Example 26. Any bounded metric space X with diam S (2 + c)ō is (c, preeudffitft Indeed, in this regime, the responder can maintain the entire space as feasible throughout the interaction by consistently replying with the constant value 8. As result, the optimal reconstruction error is simply the Chebyshev radius of X, which the reconstructor can achieve without submitting any queries.
The next two examples concern noiseless responders (i.e., 8 =0):
Example 27. The Euclidean space RD is (0, 0) -seuudoffiite Indeed, any point E RR is uniquely determined by its distances to the n + 1 vertices of a non-degenerate n-simplex (Blumenthal 1970 $2).
The same holds for any subset of R that contains such simplex. However, even in the noiseless setting (c, (0, 0), pseudo-fing Seeudo-fniteness does not hold in all metric spaces-even if the space is totally bounded:
Example 28. Let X = {0, 1 be the space of infinite binary sequences, equipped with the standard ultrametric: the distance between two sequences
(ax)eN and 3 = (Bi)sen is defined as d(a, 9) = 2-, where j is the first index for which a, * By. Then is a compact (and hence totally bounded) metric space that is not (0, 0) ()-pssuuooffiite.
Proof. We show that OPT x (T, 0) 2 2 T-1 for every T. by explicitly constructing a responder strategy. The goal is preserve a feasible set of sequences that agree on most T coordinates.
Assume that after round i, the responder has committed to most the first S bits of the secret. sequence. Given query q (qi)EN, the responder replies as follows:
36

---

If the prefix (g1...... qe) disagrees with the committed prefix, respond with the true distance 2 2, where j the first index of disagreement.
Otherwise, respond with = 2-²'-1, and define the next bit of the secret sequence as 0#41 == --41-
After T rounds, the responder has specified exactly bits. Let the reconstructor return sequence Then the responder chooses secret point x² that agrees with E on all bits except for bit T + 1, which flipped. This implies that distxx (i, x²) ) 2- yielding the lower bound.
Remark: One can further show that this lower bound is tight, and that XPTx = 2-1-1 since every informative query forces the responder reveal one additional bit.
We now present an example of non-totally bounded metric space for which the function ex fails be right-continuous.
Example 29 (Failure of right-continuity of ex). Recall that for a metric space (X, distx) the function x is defined by
ex(a) ((p(r(s) SC X, dian(S) S a
where the Chebyshev radius and diameter are
r(S) = inf sup dist x (2r, (), geX ZE8
diam(S) = sup distx (I, a.yES
Let X (Tnn Un n E N} with metric distx (In, 3n) 1+ for each n,
distx (u, v) 2 for all other distinct o
Then ex not right-continuou! 14
Proof. If a < 1, then any subset C X with diam(S) < a must be a singleton (since every nontrivial distance is > 1), hence ex (a) = 0.
For each n, let Sn {Z Vn). Then diam(S..) 1 1 n Moreover,
r(S,) inf max(distx* (En, g), dist (yn, 4)} = min 1 + 4. 2 = 11 1 xe
because choosing {I,, } yields value 1 4. while any S, is at distance from both points.
Note that any subset of X with at least three distinct points contains two points at distance 2, hence 1 S a < 1+ - the only nontrivial subsets with diam S a are has diameter Therefore, for 1 + n the pairs S₃ with & 2 n, and thus
ex(a) maxr(St) 1 m
k2n
Consequently,
lim (imex(a) = lim ex (1 + 11) 1,
while
ex(1) = 0,
so x is not right-continuous at a = 1.
We conclude the section by formally proving the equivalence between the Dinur-Nissin model and the reconstruction game the Boolean cube referenced in Example[]
Example 30 (Dinur-Nissim model). The counting-query game in the Dinur-Nissim model is equiva- lent to the distance- based game on the Boolean cube with the Hamming metric, namely, every query in one game can be simulated by most two queries in the other.
"The space X is not totally bounded: for a & every a- a-ball contains at most one point (all nonzero distances in X exceed 1), no finite a-net exists: equivalently, the only a-cover is X itself, which is infinite.
37

---

Proof. We show that the counting y game is equivalent to the distance- game on the Boolean cube (with Hamming distance) by introducing an intermediate step: both games are equivalent an inner-product game played on (=1}".
The inner-product game is defined follows. The responder chooses secret vector D (d'..... .,,) E {=1}". In each round, the reconstructor submits query vector
W (wi,..., wa) {+1}",
and the responder replies with noisy approximation of the inner product
(D', w) w.dy
Step From the Dinur-Nissim model to the inner-product game. the the dataset is binary vector D (d1....,d,)) {0, (0,1)" and each query is subset q S [n]. whose (noisy) answer is the count
model,
ag Σ di.
iéq
We can represent the subset 9 by its indicator vector Uy E {0. 1]", so that ag = (D, uy). To simulate this count using the inner-proos inner-product game on {=1}", consider the transformation
V 2 1,
which maps {0, 13"h to { Let
D' =2=2- and Wig 20g 1.
Then have the identity
DD', w)y v(D,v)) 2(D,1) 2/ql +n.
Therefore, we can recover the original count (D, v.y) by submitting two inner-product queries: one with Wi and one with the all-ones vector A similar argument gives the reverse direction.
Step I: From the inner-product game to the distance-based game. Next, we show that the inner- product game {=1}" is equivalent to the distance game on {#1}" equipped with the Hamming metric. On this space, one has the identity
distHam (x. y) 1/ v12
(2,
Hence, given the inner product (x, simple affine transformations. This correspondence between the models also modifies the noise parameters, but only in controlled manner. Since the simulation involves only affine transformations, the noise in the simulated model increases by at most a constant multiplicative factor.
recover the Hamming distance, and conversely, via
most queries and
38

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims in the abstract and introduction accurately reflect the the-
oretical contributions and limitations of the paper, including characterizations of pseudo- finiteness and bounds on the optimal error under approximate queries. See Sections] T and
2
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should elearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations of our approach are discussed throughout the paper, especially the necessity of assumptions such as total boundedness and convexity, and the difficulty of the 0 case. See Sections [nd 3
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
39

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results are stated with clearly listed assumptions, and complete proofs are provided in the full version the paper. Sketches also appear in the main text to build intuition.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: The paper does contain experiments. The results are purely theoretical and proven analytically.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
40

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
The paper does not involve data or code. All contributions are analytical.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
(ossiiccy))) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 //nips httpsscccpublcccuudccoooc
Coweeoomiisiieieeeoeeee Pollyyy))))) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: There are no experiments in this work. The paper is entirely theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not report experiments, so statistical significance does not apply.
Guidelines:
The answer NA means that the paper does not include experiments.
41

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: No compute resources were used, as the paper contains experiments computational simulations.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research complies with the NeurlPS Code of Ethics. It does not involve human subjects, data scraping, dual-use risks.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
42

---

Potential applications to privacy and location obfuscation are discussed in the introduction and motivation.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not introduce models or datasets with high risk of misuse. No safeguards necessary.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-us, should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use any external datasets or code
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
43

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperssi thoode com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not introduce new datasets, codebases, or pretrained models.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/cod//model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve human subjects or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The study does not involve human subjects and does not require IRB review.
Guidelines:
44

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: Large language models were not used as a core component of the methodol- ogy. Minor assistance in editing was provided post-development, which does not require declaration.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy (https://neure) /atp:///ecc.oaeeeeeeee/////00/3 for what should or should be described.
45


Reviews:
[{"review_id": "0Kz40OfhtF", "reviewer": "Reviewer_y9Wa", "summary": "This paper considers the problem of guessing an unknown point in a metric space,  using a series of noisy distance queries. More specifically, the paper considers a \"reconstruction game\", which involves two players: a reconstructor, who aims to accurately guess the target point, and a responder, who provides approximate distances under additive and multiplicative noise. The main goal is to study the limit of the reconstruction error in the worst case (i.e., for the most difficult point to reconstruct), assuming that the responder knows all the queries in advance, or that the recontstructor is \"deterministic\" (which, I suppose, means \"non interactive\", i.e., cannot change the queries depending on previous answers). \n\nThe paper offers two main contributions: \n\n- A characterization of the optimal approximation error that the reconstructor can obtain as the number of queries tends to infinity. This limit is shown to be related to the Chebyshev radius.\n\n- A characterization of the pseudo-finite metric spaces, which enjoy the property that the optimal reconstruction error can be achieved after a finite number of queries.  The paper shows that for bounded convex subsets of the Euclidean space, a space is pseudo-finite if and only if its dimension is one and there is no multiplicative noise.", "questions": "When you say \"deterministic reconstructor\", you mean \"non interactive\"?", "limitations": "I would recommend the authors to provide at least one detailed practical example where the problem they propose is relevant.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- The paper addresses a cute and intriguing theoretical problem, and the results are interesting\n\n- The paper is well written and seems technically solid.\n\n## Weaknesses\n\n- Although I like the paper, I am concerned about its practical relevance.  I am not convinced by the discussion provided in the introduction to justify the importance of the problem addressed in various fields. The relation with differential privacy (which is a topic I am very familiar with) seems to me rather contrived: I cannot imagine a scenario in which all the queries are fixed in advance, and, more importantly, the noise of the responder would need to adapt due to the consumption of the privacy budget. The paper also lists a series of other areas (for instance, computational geometry), for which the paper claims that the problem is relevant. On these, I cannot say for sure, because I am not an expert, but the explanation is very terse.   I would have appreciated it better to see at least one detailed practical example where the problem is relevant.", "was_revised": true, "final_justification": "After the exchange with the authors, I can see now how their approach can apply to privacy attacks like the one of  Dinur and Nissim. I understand now the power and practical applicability of the distance-based games taht the authors are proposing, and for this reason, I have raised my score.", "rebuttal": "We thank the reviewer for the thoughtful feedback and for finding the problem intriguing and the paper well-written. We now address the concerns regarding adaptivity and practical relevance.\n\nRegarding the reviewer’s question: our use of the term “deterministic reconstructor” may have caused confusion. To clarify: deterministic does not mean non-adaptive (or oblivious). In our setting, the reconstructor is fully adaptive—it chooses each query based on the interaction up to that point. The qualifier “deterministic” simply means that the query at each time step is a deterministic function of the history so far, as opposed to being sampled at random. We focus on this case primarily for simplicity of presentation; however, our results and arguments extend naturally to the more general case of randomized reconstructors as well. We will revise the paper to clarify this point.\n\nAs the reviewer noted, this misunderstanding may have contributed to the impression that the paper has limited relevance to practical problems. We hope that, after clarifying this point, the broader scope of our framework becomes more apparent.\nIn addition, while our model is indeed theoretical, it is grounded in and generalizes concrete setups with clear real-world impact. One prominent example is the reconstruction attacks of Dinur and Nissim, which played a central role in the definition of differential privacy. These attacks correspond to a special case of our model on the Boolean cube with Hamming distance. Our framework captures such attacks and extends them to a broader class of metric spaces and query types. Another example is point-location problems arising in signal processing and sensor networks, where one aims to localize a signal source based on noisy measurements. Such problems also fit naturally into our model and were a motivating example in developing it.\n\nWe note, however, that at this stage, we do not expect nor aim for our abstract results to yield immediate insights into domain-specific settings. Rather, our hope is that the framework we propose will serve as a convenient, clean, and powerful tool for understanding and reasoning about problems arising in important application domains. For example, it would be interesting to study private data analysis in this setting—namely, to what extent the responder can retain uncertainty about its secret input point $x$ while still providing sufficiently accurate answers. Quantifying such uncertainty in a geometric context is a compelling and nontrivial challenge, and we hope that future work will develop this direction further. In contrast, the theorems in the present work are centered on the reconstructor’s perspective and aim to establish basic capabilities and limitations of learning from noisy metric feedback.\n\nTo summarize, this is indeed a theoretical contribution, but one that unifies—through a learning-theoretic formulation—a variety of reconstruction problems that have both been studied in practice and shown to be of significant practical impact. We believe and hope that by distilling the common structure underlying these problems, our framework provides a useful foundation for future theoretical and applied work alike."}, {"review_id": "skHL7XMFsh", "reviewer": "Reviewer_6CpE", "summary": "This paper studies a two-player reconstruction game to locate an unknown target point $x$ in a metric space via sequential (approximate) distance queries. Concretely, in each round, the reconstructor queries a point $q$ in the space; then the responder replies with a noisy distance $\\hat{d}$ between $x$ and $q$, satisfying $(1+\\varepsilon)$-multiplicative plus $\\delta$-additive distortion bounds. The output of the game is the best reconstructor's worst-case reconstruction error. This paper focuses on studying the rate and limits of such an error as the number of rounds goes to infinity.", "questions": "1. In my opinion, the main contribution of this paper is initiating the study on the reconstruction problem from a geometric perspective. Given this, I think it is crucial that the authors clearly discuss all related work and the novelty of the perspective. However, I find that all related works discussed in Appendix A to be not so related to this paper -- in particular, I'm curious whether none of them study the convergence rates of the reconstruction error as in this paper? Moreover, are the authors aware of any additional related work that also studies this in a similar metric-geometry point of view?\n\n2. In the remark on line 77: A Priori vs. A Posteriori Responder, it is stated that the responder waits until *all* queries have been seen before selecting the secret point. Does this mean the constructor has to issue all queries in one batch before seeing any response, i.e. the queries cannot be adaptive? In this sense, the reconstruction game is essentially an one-round game? This confuses me a little since in Section 1.1 Problem Setup, the game is described as being played for T interactive rounds. And reading the following text of the paper, I think the game is still played in T-round. I suggest the authors to clarify the remark a bit to avoid any confusion.", "limitations": "Yes, the limitations are clearly discussed. The authors also point out multiple potential future directions.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strength**:\n\n- In my opinion, the authors present this paper as proposing a unified, geometric lens to study the reconstruction problem. I find the viewpoint of interpreting the transcript of the reconstruction game as determining a feasible region interesting; indeed, it elegantly bridges together classical metric‐geometry and the learning problem. \n\n- The main result of this paper (Theorem 1) tightly characterizes the best possible reconstruction error any reconstructor can guarantee in terms of the Chebyshev radius. As the Chebyshev radius is a classical and natural concept in geometry, I find such a characterization nice and clean. In particular, the authors show that the the best attainable reconstruction error is exactly the worst‐case Chebyshev radius over sets of diameter $(2+\\varepsilon)\\delta$. \n\n**Weakness**:\n\n- Although this paper characterizes the asymptotic optimum of the reconstruction error, it does not provide quantitative rates at which the error converges to its limit, beyond identifying spaces that are \"pseudo‐finite\" versus those that are not. It would be more satisfying if there's more discussion on the precise finite convergence bounds.\n\n- While this paper discuss the case when the multiplicative error factor $\\varepsilon = 0$, it seems that there's no discussion on the case when the additive error $\\delta = 0$. In my opinion, the later feels like a more interesting case, as e.g., in approximate similarity search, it is usually more desirable to achieves a multiplicative $(1+\\varepsilon)$ error guarantee, as opposed to an additive error guarantee.\n\n- Besides the observation of interpreting the reconstruction game as determining a feasible region, the proof to Theorem 1 feels simple and straight-forward. On the other hand, while the proof ideas to Theorem 4 are more involved, they only lead to results restricted to convex subsets of $\\mathbb{R}^n$, leaving the broader landscape of totally bounded metric spaces unsettled.", "was_revised": true, "final_justification": "The authors comprehensively answer my questions. The discussion on the convergence rates and multiplicative noise is interesting and insightful. And I agree that \"the proof of Theorem 1 is intuitive reflects that it captures the `correct’ characterization.\"", "rebuttal": "We thank the reviewer for the thoughtful and constructive feedback, and for recognizing the value of our geometric framing and the clean characterization of the reconstruction error in Theorem 1.\n\n**On convergence rates and multiplicative noise**\n\nThe reviewer raises two important and closely related points: the lack of explicit discussion on quantitative convergence rates, and the apparent omission of the case of purely multiplicative noise ($\\delta = 0$ and $\\epsilon >0$). We thank the reviewer for highlighting both issues. While these aspects were not sufficiently emphasized in the current version, our results do apply to the purely multiplicative case and offer insights into convergence rates. We will revise the manuscript to address both points more clearly, as detailed below.\n\nFirst, we note that Theorem 1 includes the case of $\\delta = 0$ as a special case in its characterization of $\\mathrm{OPT}$.\nIn particular, it implies that $\\mathrm{OPT}(\\epsilon, 0) = 0$.\n\nAs for Theorem 4, while not stated explicitly, our proof yields a tight exponential bound on the convergence rate of $\\mathrm{OPT}(\\epsilon, 0)$ in the case of purely multiplicative noise (i.e., $\\delta = 0$ and $\\epsilon >0$). It follows from inspecting our argument that Euclidean spaces are not pseudo-finite: by definition, a space is pseudo-finite if the optimal reconstruction error $\\mathrm{OPT}(T, \\epsilon, \\delta)$ reaches its limiting value in a finite number of rounds. Thus, establishing that Euclidean spaces are not pseudo-finite amounts to proving a non-trivial lower bound on the convergence rate. A closer look at our construction shows that this lower bound is exponential when $\\epsilon >0$.\n\nA matching exponential upper bound in the purely multiplicative case follows from standard space-partitioning techniques in computational geometry: the reconstructor can query a uniform grid of fixed size (depending only on the dimension), identify the grid point with the smallest reported distance, and then refine the search by querying a new fixed-size grid centered around that point and scaled to a smaller neighborhood. Repeating this process geometrically shrinks the feasible region, yielding an exponential upper bound on $\\mathrm{OPT}(\\epsilon, 0)$.\n\nWe note in passing that the case of $\\epsilon = 0$ and  $\\delta > 0$ is more subtle. Our current analysis yields only a double-exponential lower bound on $\\mathrm{OPT}$, and it remains open whether this rate is tight.\n\nMore broadly, convergence rates outside Euclidean spaces appear to depend heavily on the geometry. We expect that sharp bounds will require case-specific analysis, and we identify this as an important open direction in Question 5.\n\n⸻\n\n**On the proof of Theorem 1**\n\nWhile we agree that the proof of Theorem 1 is intuitive once the right definitions are in place, we respectfully note that this intuitiveness reflects the fact that Theorem 1 captures the `correct’ characterization. As is often the case in mathematics, a proof may appear straightforward once the key concepts are established—but discovering those concepts can require significant insight.\n\nIn our case, it took considerable effort to identify what governs $\\mathrm{OPT}$ in this reconstruction game. Two key observations guided us: (i) if the reconstructor is allowed to query all points in the space, then the feasible set has diameter at most $\\delta\\cdot(\\epsilon+2)$, and (ii) the responder can maintain any set of that diameter as feasible for all $T$. These two facts pointed toward the Chebyshev radius as the central quantity, and once this connection was made, the form of the characterization followed naturally. Our effort in uncovering this structure is further reflected in the wide range of metric spaces we analyzed—both to test the sharpness of our characterization and to understand its implications. We included over five distinct examples in the paper, spanning diverse geometries, and discussed others along the way.\n\nThe proof may now seem smooth, but this reflects the fact that Theorem 1 captures the correct structure of the problem. We hope the reviewer will recognize the mathematical effort and non-triviality involved in identifying the right characterization.\n\n⸻\n\n**On related work**\n\nThe reviewer raises an important point regarding the absence of references on convergence rates for the reconstruction error $\\mathrm{OPT}(\\epsilon, \\delta)$. We emphasize that this reflects a genuine gap in the literature rather than an oversight. While preparing the paper, we searched extensively for prior work addressing convergence rates in the general setting we consider and were surprised to find none.\n\nIn particular, we consulted several experts across both broad areas—such as theoretical computer science, combinatorics, and geometry—and more specific fields, including learning theory, computational geometry, and differential privacy. These conversations confirmed not only the lack of direct prior work on the problem, but also that the question appears natural and its absence in the literature is somewhat surprising. We also conducted extensive literature searches using academic databases and large language models (e.g., ChatGPT and Gemini). Throughout the development of the paper, we continuously refined our Google searches with updated keywords—for example, after identifying the relevance of the Chebyshev radius and Jung’s constant, we included these terms in our queries.\n\nThese efforts did not uncover prior work directly addressing convergence rates of $\\mathrm{OPT}(\\epsilon, \\delta)$, though they did bring to our attention related but more specialized notions. For example, we discovered the notion of sequential dimension in graphs through these searches. In contrast, our work was directly inspired by earlier reconstruction attacks in differential privacy, such as the Dinur–Nissim framework, which we were already aware of. We discuss both of these connections, as well as others, in Appendix A.\n\n⸻\n\n**On the responder model and adaptivity**\n\nThe reviewer asks for clarification regarding the remark on line 77 about the “a posteriori” responder, which states that the responder selects the secret point only after all queries have been issued. The concern is whether this implies that the reconstructor must submit all queries at once (i.e., non-adaptively), which seems inconsistent with the T-round interactive game described in Section 1.1.\n\nWe thank the reviewer for pointing out this potential confusion. To clarify: in our formulation, both the reconstructor and the responder are allowed to act adaptively. The game proceeds for T rounds, during which the reconstructor chooses each query based on past responses, and the responder chooses each response based on all queries and its chosen secret point.\n\nThe distinction between a priori and a posteriori responder models concerns when the responder commits to the secret point. In the a priori model, the responder selects the secret point before seeing the queries. In the a posteriori model, the responder waits until all queries are revealed before choosing the secret point, giving it an additional degree of adaptivity. This latter setting is the one we focus on in the paper.\n\nWe will revise the remark to clarify this point and avoid confusion."}, {"review_id": "f0n2vnlyTj", "reviewer": "Reviewer_WJ4i", "summary": "This paper studies what the authors refer to as “the reconstruction game” which is played over a metric space $(X,dist_X)$ between a reconstructor and a responder and is defined as follows: at each time $t$, the reconstructor submits a query $q_t \\in X$, and the responder returns a $(1+\\epsilon)$-multiplicative, $\\delta$-additive “approximate distance” $\\hat{d}_t$. After $T$ steps, the feasible region is the set of points in $X$ whose distance to each $q_t$ is approximated by $\\hat{d}_t$. At the end of the game, the reconstructor picks a “guess” $x \\in X$, and the responder then chooses a final point $y$ in the feasible region (required to be non-empty). The goal of the reconstructor is to carefully choose queries in order to minimize the distance between the final points $x$ and $y$, and the responder is an adversary which is trying to maximize this distance.\n\nThe paper is concerned with what is the minimum distance achievable by the reconstructor in the limit as $T \\to \\infty$. This optimum distance depends on the approximation parameters $\\epsilon,\\delta$ (the leway afforded to the responder) as well as properties of the metric, name the Chebyshev radius. In particular, their Theorem 1 shows that for many natural metrics, the optimum distance is $\\Theta(\\delta(2+\\epsilon))$. \n\nNext, the authors are interested in understanding the rate of convergence to this optimum value, although this turns out to be challenging. As a first step, they seek to understand for which spaces exact convergence to the optimum occurs after a finite number of steps (finite $T$), and call these spaces “pseudo-finite”. Their second main result (Theorem 4) is that for bounded convex sets in $\\mathbb{R}^n$, unless $\\epsilon = 0$ or the dimension of the set is $1$, the set is not pseudo-finite.", "questions": "Main questions:\n\nWhat are some of the barriers to understanding the rate of convergence to the optimum? Are there natural special cases or ways to simplify the problem that make it easier?\nWhat happens if the responder is not adversarial? I.e. what if a hidden point is fixed up-front (as in the remark) and the response to each query is some random noisy approximation of the distance? Does this make things significantly easier? \n\n\nMinor questions, typos, and comments:\n\nThere seem to be some numbering discrepancies between the main and full versions. E.g. the full version refers to “Example 6” which I think is supposed to mean “Example 1”.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths: To me, the reconstruction game considered in this work is very natural, and it is surprising to me that it seems like there has been little prior work from a theoretical perspective. Therefore, I consider it to be good in terms of originality. The paper establishes some basic and tight results which seem fundamental. I also think it is well written and clear.\n\nWeaknesses: The paper does not address rate of convergence, which might be more practical and significant, although I recognize this may be very challenging.", "was_revised": true, "final_justification": "I believe this paper is well written and contains nice results. I believe it is above the bar for acceptance and I am keeping my score a 5.", "rebuttal": "We thank the reviewer for taking the time to read and appreciate our paper, and for the positive feedback.\n\nWe acknowledge the presence of some numbering inconsistencies and will make sure to correct them in the next version of the paper.\nThe reviewer also raised a couple of interesting questions that we are happy to address.\n\n**On rates of convergence to $\\mathrm{OPT}$ in Euclidean spaces.**\n\nThe reviewer was interested in identifying the main obstacles to determining the rate of convergence to $\\mathrm{OPT}$. We believe that, in Euclidean spaces, the main challenge lies in proving an upper bound, while the current lower bound in Theorem 4 is likely close to optimal—though a tighter bound may still be possible.\n\nIt is important to note that our analysis already yields tight convergence bounds in certain cases. In particular, in the setting of purely multiplicative noise (i.e., $\\delta = 0$ and $\\epsilon > 0$), our proof shows that convex Euclidean spaces are not pseudo-finite—that is, the approximation error $\\mathrm{OPT}_T(\\epsilon, \\delta)$ does not stabilize after finitely many rounds. A closer inspection of the argument reveals that the convergence rate is at least exponential in this case.\n\nA matching exponential upper bound can be derived using standard space-partitioning techniques from computational geometry: the reconstructor queries a fixed-resolution grid (depending only on the dimension), identifies the grid point with the smallest reported distance, and then refines the search over successively smaller neighborhoods. This strategy yields an exponential decrease in reconstruction error over time.\n\nWe will add a remark in the next revision to clarify that our analysis already captures this case.\n\nThe case of purely additive noise—i.e., $\\delta > 0$ and $\\epsilon = 0$—is substantially more subtle. Our proof of Theorem 4 provides a double-exponential lower bound on the convergence rate when the dimension $d > 1$, and it remains open whether this rate is tight. We suspect that it might be, but proving a matching upper bound is challenging. The main difficulty lies in controlling the Chebyshev radius of the feasible region: while the diameter can be reduced relatively easily through adaptive querying, the Chebyshev radius is more sensitive to the internal geometry of the region. This challenge is compounded by the fact that the feasible region is defined as the intersection of differences of balls—a geometrically intricate and non-convex set.\n\nTo gain traction on this problem, we are currently investigating a restricted variant in which the reconstructor issues linear queries (which are interesting in their own right).; that is, the reconsturctor selects a direction (i.e. a unit vector) and receives a noisy approximation of the inner product with the secret point. In this setting, the feasible region becomes a convex polytope, making it more amenable to geometric analysis. Interestingly, our characterization of $\\mathrm{OPT}$ continues to hold in this linear-query model. We hope that progress in this simplified setting will yield insights applicable to the more general case of distance queries.\n\n\n**On relaxation of the model.**\n\nThe reviewer also asked whether the setup becomes easier to analyze—or allows for better approximations—when the responder is not adversarial but instead adds fixed noise to the true answer. This is a very natural and important question.\n\nThe answer is yes: when the responder adds a known type of noise in each round—such as independent noise with mean zero—the problem becomes significantly more tractable, and the reconstruction error can decrease substantially. Under suitable assumptions, the error can even converge to zero with high probability.\n\nFor instance, in Euclidean space $\\mathbb{R}^d$, if each response is perturbed by independent mean-zero noise, the reconstructor can repeat the same query point multiple times and average the responses. This effectively denoises the answers, and by submitting $d+1$ affinely independent queries and averaging appropriately, the reconstructor can approximate the distances—and hence the hidden point—with arbitrarily high accuracy.\n\nThis relaxed setting raises several interesting directions for future work, such as studying how different noise distributions affect reconstruction, and how the reconstructor’s level of knowledge (full, partial, or none) about the noise impacts the process. We thank the reviewer for this insightful suggestion and will include it as a proposed direction in the revised version (with an acknowledgment to the reviewer).\n\nFinally, we note that a related variant—discussed earlier in our response on convergence rates—considers linear queries rather than distance queries. In this version, the reconstructor submits directions $v_i$, and the responder returns noisy inner products with the hidden point. This setup leads to a convex feasible region, making it more amenable to analysis."}, {"review_id": "mzzzNhqQ8V", "reviewer": "Reviewer_M3JV", "summary": "The work studies a reconstruction game between a reconstructor and a responder. The reconstructor can query points in a metric space, and the responder must approximately reveal the distance of the query point to a fixed target point. The goal of the reconstructor is to figure out the location of the target point up to small error. The authors characterize the min-max optimal error in terms of the Chebyshev radius of the metric space. The problem derives some motivation from reconstruction attacks in privacy applications.", "questions": "1. Does the main result lead to improved bounds in the context of differential privacy? If not, would it at least give a simpler or cleaner way to prove existing results?\n2. In differential privacy applications, the noise scales with the number of queries. In contrast, in the formalism of the paper, the parameters epsilon and delta are fixed. How do you apply the theory to cases where epsilon and delta are a function of the number of queries?\n3. Do your results apply to varying epsilon and delta at each step? This could be interesting in applications where different noise levels are used at each step, e.g., gradient-based queries whose norm vary at each update step.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well written. The mathematical formulation is elegant and natural. The authors provide ample discussion about the motivation and interpretation of the model. \n\nThe main theorem is elegant as it exactly characterizes the error exactly in terms of a natural geometric notion, the Chebyshev radius. Under reasonable additional assumptions this gives upper and lower bounds on the min-max error that match up to constant factor.\n\nThere's a nice connection between this problem and Dinur-Nissim style reconstruction problems that are relevant to privacy problems, in particular, differential privacy. However, the paper does not present any new results on privacy. I would've liked to see some new applications either to privacy or other areas where this problem is relevant. The main characterization is nice, but I was hoping to see some new results in specific settings based on this result. \n\nAs a consequence, the paper feels a bit more like a SODA/SoCG paper than a NeurIPS paper. Additional connections to machine learning applications would've been nice. The additional results on pseudo-finiteness were a bit too theoretical for my taste as an outsider to this area.\n\nTo summarize, this work is an elegant theory paper on a natural question about metric spaces with somewhat limited applications to machine learning.", "was_revised": true, "final_justification": "I raised my score based on the authors' discussion with other reviewers.\n\nMy enthusiasm is throttled by the lack of learning-theoretic applications, and the lack of any theoretical results about the dependence on the number of steps.", "rebuttal": "**Response to weaknesses**\n\nWe thank the reviewer for the thoughtful and encouraging feedback, and for highlighting the elegance of the model and the main results. \n\nThe reviewer raises two main concerns: the lack of concrete applications—especially to privacy—and the paper’s fit to the NeurIPS audience. \n\nWe would like to clarify that the primary aim of this work is to identify and study a new interactive learning framework: reconstruction in metric spaces. This abstract formulation captures a variety of contexts, ranging from point-location from noisy signals to Dinur–Nissim–style reconstruction problems relevant to privacy. Within this framework, we analyze fundamental questions about the optimal performance achievable by the reconstructor, establishing baseline results such as Theorem 1, which exactly characterizes the reconstruction error ($\\mathrm{OPT}$). \n\nAt this early stage, we do not expect these abstract results to yield immediate insights into domain-specific tasks such as privacy-preserving data analysis. That said, we do anticipate such insights to emerge as the theory matures. Moreover, this paper focuses on the reconstructor’s perspective. To study contexts such as private data analysis within this framework, it is essential to consider the responder’s perspective—that is, the agent who answers queries. In privacy-related applications, the responder seeks to provide approximately accurate answers while protecting sensitive data. Just defining what it means for the responder to protect the data, and how to quantify this formally in such a general setting, is itself an interesting challenge. Applications and insights related to differential privacy and private data analysis more broadly are goals we hope to pursue once these foundational questions are addressed. We view the study of the responder’s perspective as an important direction for future work. \n\n*Regarding venue fit:* while our framework naturally encompasses problems of interest to the SoDA and SoCG communities, our approach is grounded in learning theory. The reconstruction game is, at its core, an interactive learning problem, and one of our key contributions is the learning-theoretic characterization of $\\mathrm{OPT}$—analogous to Bayes-optimality in standard supervised learning. We therefore believe NeurIPS, with its strong tradition of foundational work in learning theory, is an appropriate venue for this work.\n\n**Responses to questions**\n\n- Question 1: Does the main result lead to improved bounds in differential privacy? If not, does it at least simplify existing proofs?\n\nAs noted above, the technical content of this work does not concern differential privacy. Our focus is on analyzing the optimal approximation error from the reconstructor’s perspective. Applications to privacy relate instead to the responder’s perspective—where the goal is to provide approximately correct answers while maintaining uncertainty about the secret point. This aspect is not addressed in the present work, but we view its formalization as an important direction for future research. Once developed, it may lead to meaningful connections with differential privacy.\n\n- Question 2: In differential-privacy applications, noise scales with the number of queries, whereas epsilon and delta are fixed in your formalism. How does the theory apply when epsilon and delta depend on the query count?\n\nThis question is closely related to understanding convergence rates to $\\mathrm{OPT}(\\epsilon, \\delta)$. Theorem 1 applies in this setting as well: $\\mathrm{OPT}(\\epsilon, \\delta)$ remains a lower bound even when epsilon and delta depend on the number of queries T. However, the tightness of this bound depends on how fast the reconstructor can approach it. For instance, Theorem 4 shows that in Euclidean spaces of dimension $\\ge 2$, this lower bound is never tight unless the noise parameters are zero. As we note in the paper, finding quantitative bounds on these convergence rates in natural metric spaces is an interesting direction for future research. (See also our response to Reviewer 6CpE, where we derive some quantitative bounds that follow from our results.)\n\n- Question 3: Do the results extend to epsilon and delta that vary at each step?\n\nIf the sequence of noise levels $(\\epsilon_t, \\delta_t)$ is non-increasing over time (i.e., the noise weakens or stays constant as the game progresses), then both Theorem 1 as well as Theorem 4 apply with the limiting values of $\\epsilon_t$ and $\\delta_t$ (with the reservation that if the limit is not attained in finite time, then OPT can also never be attained in a finite number of steps).\n\nFor more general sequences, the behavior can be very different. For example, in $\\mathbb R^d$, if there are $d + 1$ time steps where both $\\epsilon_t$ and $\\delta_t$ are zero—and the reconstructor knows which time steps these are—it can locate the secret point exactly by querying an affinely independent set of $d + 1$ points at those times. In such cases, the information available can far exceed what is predicted by our lower bounds.\n\nIt would be interesting to study this question further for natural or structured sequences $(\\epsilon_t, \\delta_t)$, and also in settings where the reconstructor has only partial information or uncertainty about the values of $\\epsilon_t$ and $\\delta_t$ at each step."}]

Author rebuttal:

Meta-review: This paper considers a "reconstruction game", which involves two players: a reconstructor, who aims to accurately guess the target point, and a responder, who provides approximate distances under additive and multiplicative noise. The main goal is to study the limit of the reconstruction error in the worst case (i.e., for the most difficult point to reconstruct), assuming that the responder knows all the queries in advance, or that the recontstructor is "deterministic".

Strengths: This paper characterizes the optimal approximation error that the reconstructor can obtain as the number of queries tends to infinity. This limit is shown to be related to the Chebyshev radius. The paper  shows that in the pseudo-finite metric spaces the optimal reconstruction error can be achieved after a finite number of queries. 

There are some concerns about the practicality of the paper, the reviewers agree that this is an exciting result for a novel formulation of a problem of interest.
Decision: Accept (spotlight)