The Andoni–Krauthgamer–Razenshteyn characterization of sketchable norms fails for sketchable metrics

DOI10.1137/1.9781611975482.109zbMath1432.68372arXiv1810.04321OpenAlexW4288851180MaRDI QIDQ5236293

Subhash A. Khot, Assaf Naor

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.04321

Mathematics Subject Classification ID

Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Metric embeddings as related to computational problems and algorithms (68R12)