Review for NeurIPS paper: On Adaptive Distance Estimation

Summary and Contributions: The paper presents a data structure that can output a (1 eps)-approximation to the Euclidean distance from a query point q in R d to each of n preprocessed points in time O(n/eps 2) per query q, where for simplicity I assume d n and omit logarithmic factors. The method works not only for Euclidean distances, but for every l_p norm, 0 p 2. In comparison, a straightforward computation takes time O(nd). The key feature of this randomized data structure is that it works even for an *adaptive* sequence queries. This is trivial for deterministic data structures, but might not hold for randomized ones, including all currently known ones, which are all variants of the JL dimension reduction from dimension d to 1/eps 2. This robustness to adaptive queries is becoming increasingly important, if not crucial, in modern data analysis, which relies heavily on applying such procedures repeatedly and is prone to correlations. The solution is relatively simple technically.