Reconstruction and Secrecy under Approximate Distance Queries
Shay Moran and Elizaveta Nesterova
考虑使用近似距离查询定位未知目标点的任务:在每一轮中,重建器选择一个查询点,并接收其距离目标的嘈杂版本。 这个问题自然出现在各种环境中,从GPS和传感器网络中的本地化到隐私感知数据访问,并跨越了各种各样的度量空间。 从重建者(寻求准确恢复)和响应者(旨在限制信息披露,例如出于隐私或安全原因)的角度来看,这是相关的。 我们通过学习理论镜头研究这种重建游戏,专注于最佳重建误差的速度和极限。 我们的第一个结果提供了切比舍夫半径的最佳误差的紧密几何特征,这是几何学的经典概念。 此表征适用于所有紧凑度量空间(事实上,甚至适用于所有完全边界的空间),并产生自然度量空间的显式公式。 我们的第二个结果解决了重建的渐近行为,区分了伪有限空间 - 在有限多次查询后达到最佳误差 - 以及近似曲线表现出非平凡衰减的空间。 我们表征了 convex Euclidean 空间的伪有限性。
Consider the task of locating an unknown target point using approximate distance queries: in each round, a reconstructor selects a query point and receives a noisy version of its distance to the target. This problem arises naturally in various contexts ranging from localization in GPS and sensor networks to privacy-aware data access, and spans a wide variety of metric spaces. It is relevant from the perspective of both the reconstructor (seeking accurate recovery) and the responder (aiming to li...