Abstract
A line of work has looked at the problem of recovering an input from distance queries. In this setting, there is an unknown sequence s ∈ {0,1}^{≤ n}, and one chooses a set of queries y ∈ {0,1}^?(n) and receives d(s,y) for a distance function d. The goal is to make as few queries as possible to recover s. Although this problem is wellstudied for decomposable distances, i.e., distances of the form d(s,y) = ∑_{i=1}^n f(s_i, y_i) for some function f, which includes the important cases of Hamming distance, ?_pnorms, and Mestimators, to the best of our knowledge this problem has not been studied for nondecomposable distances, for which there are important special cases such as edit distance, dynamic time warping (DTW), Fréchet distance, earth mover’s distance, and so on. We initiate the study and develop a general framework for such distances. Interestingly, for some distances such as DTW or Fréchet, exact recovery of the sequence s is provably impossible, and so we show by allowing the characters in y to be drawn from a slightly larger alphabet this then becomes possible. In a number of cases we obtain optimal or nearoptimal query complexity. We also study the role of adaptivity for a number of different distance functions. One motivation for understanding nonadaptivity is that the query sequence can be fixed and the distances of the input to the queries provide a nonlinear embedding of the input, which can be used in downstream applications involving, e.g., neural networks for natural language processing.
BibTeX  Entry
@InProceedings{hu_et_al:LIPIcs.ITCS.2023.73,
author = {Hu, Zhuangfei and Li, Xinda and Woodruff, David P. and Zhang, Hongyang and Zhang, Shufan},
title = {{Recovery from NonDecomposable Distance Oracles}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {73:173:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17576},
URN = {urn:nbn:de:0030drops175767},
doi = {10.4230/LIPIcs.ITCS.2023.73},
annote = {Keywords: Sequence Recovery, Edit Distance, DTW Distance, Fr\'{e}chet Distance}
}
Keywords: 

Sequence Recovery, Edit Distance, DTW Distance, Fréchet Distance 
Collection: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023) 
Issue Date: 

2023 
Date of publication: 

01.02.2023 