# Fast Metric Decompositions in High Dimension

Preprint · Robert Krauthgamer, Asaf Petruschka, Nir Petruschka

- Archive id: arxiv:2608.22488
- Published: 2026-08-23
- arXiv: https://arxiv.org/abs/2608.22488
- Source URL: https://arxiv.org/abs/2608.22488
- PDF: https://arxiv.org/pdf/2608.22488
- Provenance: arxiv

## Abstract

Metric decompositions are a fundamental tool in the design of algorithms involving distances. We study fast algorithms for sampling from probabilistic metric decompositions of $n$-point sets in $\\ell\_\\infty$ and $\\ell\_2$ spaces of high dimension $d$. For $\\ell\_\\infty$, we design a padded-decomposition algorithm that runs in time $\\tilde{O}(nd^2)$, which is near-linear in $n$, and achieves padding parameter $\\tilde{O}(\\log n)$. Our algorithm constructs a new sparse neighborhood cover that is based on geometric properties of $\\ell\_\\infty$ \[Indyk, JCSS'01\], and utilizes recent reductions between covers and decompositions \[Conroy and Filtser, STOC'25\]. For $\\ell\_2$, we design a separating-decomposition algorithm that achieves near optimal separation $\\tilde{O}(\\sqrt{\\log n})$ in almost-linear time $n^{1+o(1)}$. Our bounds improve over known algorithms with similar running time by a factor $Ω(\\sqrt{\\log n})$, and the techniques have additional applications to spanners and nearest-neighbor search.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.