Reconstructing a point set from a random subset of its pairwise distances

Let V be a set of n points on the real line. Suppose that each pairwise distance isknown independently with probability p. How much of V can be reconstructed up to isometry? Weprove that p = (log n)/n is a sharp threshold for reconstructing all of V , which improves a resultof Benjamini and Tzalik. This follows from a hitting time result for the random process where thepairwise distances are revealed one by one uniformly at random. We also show that 1/n is a weakthreshold for reconstructing a linear proportion of V.