Optimal (Euclidean) Metric Compression
From MaRDI portal
Publication:5080486
DOI10.1137/20M1371324OpenAlexW3203560892WikidataQ114074150 ScholiaQ114074150MaRDI QIDQ5080486FDOQ5080486
Authors: Tal Wagner, Piotr Indyk 
Publication date: 31 May 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2110.03152
Data structures (68P05) Discrete geometry (52C99) Metric embeddings as related to computational problems and algorithms (68R12)
Cites Work
- Extensions of Lipschitz mappings into a Hilbert space
- The space complexity of approximating the frequency moments
- Approximate distance oracles
- A tight bound on approximating arbitrary metrics by tree metrics
- On sparse spanners of weighted graphs
- Graph spanners
- Title not available (Why is that?)
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
- Approximate nearest neighbor: towards removing the curse of dimensionality
- Euclidean quotients of finite metric spaces
- Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
- Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
- Title not available (Why is that?)
- Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error
- On the distortion required for embedding finite metric spaces into normed spaces
- Probabilistic clustering of high dimensional norms
- Approximate Distance Oracles with Improved Bounds
- Fast Binary Embeddings and Quantized Compressed Sensing with Structured Matrices
- Optimal terminal dimensionality reduction in Euclidean space
- Nonlinear dimension reduction via outer Bi-Lipschitz extensions
- Near-Optimal (Euclidean) Metric Compression
Cited In (2)
This page was built for publication: Optimal (Euclidean) Metric Compression
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080486)
