| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

11. Finding a Planted Vector


    1. Add remark

      Problem 11.1.

      [Erik Waingarten] Suppose we have $n$ vectors in the unit sphere of $\ell_2^{O(\log n)}$ drawn uniformly at random. We place an extra vector at distance $0.1$ from one of the random vectors. Can this vector be found in $O(n \text{ polylog } n)$ time?

          Cite this as: AimPL: Metric embeddings, available at http://aimpl.org/metricembeddings.