  An outstanding open question posed by Guha and Indyk in 2006 asks to
characterize metric spaces in which distances can be estimated using efficient
sketches. Specifically, we say that a sketching algorithm is efficient if it
achieves constant approximation using constant sketch size. A well-known result
of Indyk (J. ACM, 2006) implies that a metric that admits a constant-distortion
embedding into $\ell_p$ for $p\in(0,2]$ also admits an efficient sketching
scheme. But is the converse true, i.e., is embedding into $\ell_p$ the only way
to achieve efficient sketching?
  We address these questions for the important special case of normed spaces,
by providing an almost complete characterization of sketching in terms of
embeddings. In particular, we prove that a finite-dimensional normed space
allows efficient sketches if and only if it embeds (linearly) into
$\ell_{1-\varepsilon}$ with constant distortion. We further prove that for
norms that are closed under sum-product, efficient sketching is equivalent to
embedding into $\ell_1$ with constant distortion. Examples of such norms
include the Earth Mover's Distance (specifically its norm variant, called
Kantorovich-Rubinstein norm), and the trace norm (a.k.a. Schatten $1$-norm or
the nuclear norm). Using known non-embeddability theorems for these norms by
Naor and Schechtman (SICOMP, 2007) and by Pisier (Compositio. Math., 1978), we
then conclude that these spaces do not admit efficient sketches either, making
progress towards answering another open question posed by Indyk in 2006.
  Finally, we observe that resolving whether "sketching is equivalent to
embedding into $\ell_1$ for general norms" (i.e., without the above
restriction) is equivalent to resolving a well-known open problem in Functional
Analysis posed by Kwapien in 1969.
