## Abstract

Andoni, Krauthgamer and Razenshteyn (AKR) proved (STOC’15) that a finite-dimensional normed space (X, k·kX) admits a O(1) sketching algorithm (namely, with O(1) sketch size and O(1) approximation) if and only if for every ε ∈ (0, 1) there exist α > 1 and an embedding f : X → `_{1}−ε such that kx − ykX 6 kf(x) − f(y)k_{1}−_{ε} 6 αkx − yk_{X} for all x, y ∈ X. The”if part” of this theorem follows from a sketching algorithm of Indyk (FOCS 2000). The contribution of AKR is therefore to demonstrate that the mere availability of a sketching algorithm implies the existence of the aforementioned geometric realization. Indyk’s algorithm shows that the”if part” of the AKR characterization holds true for any metric space whatsoever, i.e., the existence of an embedding as above implies sketchability even when X is not a normed space. Due to this, a natural question that AKR posed was whether the assumption that the underlying space is a normed space is needed for their characterization of sketchability. We resolve this question by proving that for arbitrarily large n ∈ N there is an n-point metric space (M(n), d_{M}(n_{)}) which is O(1)-sketchable yet for every ε ∈ (0, ^{1}_{2} ), if α(n) > 1 and f_{n} : M(n) → `_{1}−_{ε} are such that d_{M}(n_{)}(x, y) 6 kf_{n}(x) − f_{n}(y)k_{1}−_{ε} 6 α(n)d_{M}(n_{)}(x, y) for all x, y ∈ M(n), then necessarily lim_{n→∞} α(n) = ∞.

Original language | English (US) |
---|---|

Pages | 1814-1824 |

Number of pages | 11 |

DOIs | |

State | Published - 2019 |

Event | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States Duration: Jan 6 2019 → Jan 9 2019 |

### Conference

Conference | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 |
---|---|

Country/Territory | United States |

City | San Diego |

Period | 1/6/19 → 1/9/19 |

## ASJC Scopus subject areas

- Software
- Mathematics(all)