The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics

DOI10.1007/978-3-030-61887-2_8zbMath1490.46022MaRDI QIDQ3384132

Assaf Naor, Subhash A. Khot

Publication date: 14 December 2021

Published in: Springer Optimization and Its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-61887-2_8

zbMATH Keywords

sketchable metric; sketchable norm; sketching algorithm

Mathematics Subject Classification ID

46B85: Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science

68R12: Metric embeddings as related to computational problems and algorithms