Recovery from Non-Decomposable Distance Oracles

Zhuangfei Hu, Xinda Li, David P. Woodruff +2

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\in \{0,1{\}}^{\le n}$, and one chooses a set…