The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics
From MaRDI portal
Publication:3384132
DOI10.1007/978-3-030-61887-2_8zbMath1490.46022OpenAlexW2896073191MaRDI QIDQ3384132
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
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)
Cites Work
- Realization of metric spaces as inverse limits, and bilipschitz embedding in \(L_1\)
- Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\)
- Uniform embeddings of metric spaces and of Banach spaces into Hilbert spaces
- Banach spaces embedding into \(L_ 0\)
- The space complexity of approximating the frequency moments
- Influences of variables and threshold intervals under group symmetries
- Random walk in random groups.
- Lectures on analysis on metric spaces
- Vertical perimeter versus horizontal perimeter
- Gaussian noise sensitivity and Fourier tails
- Euclidean quotients of finite metric spaces
- On the distribution of the Fourier spectrum of Boolean functions
- An average John theorem
- Nonembeddability theorems via Fourier analysis
- Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
- Integrality gaps for sparsest cut and minimum linear arrangement problems
- L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry
- Stable distributions, pseudorandom generators, embeddings, and data stream computation
- Expander graphs and their applications
- The Smoothed Complexity of Edit Distance
- Space lower bounds for distance approximation in the data stream model
- Improved Lower Bounds for Embeddings into $L_1$
- Plongements lipschitziens dans ${\bbfR}\sp n$
- Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
- Sketching and Embedding are Equivalent for Norms
- Analysis of Boolean Functions
- Euclidean distortion and the sparsest cut
- A PRG for lipschitz functions of polynomials with applications to sparsest cut
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
- Geometry of cuts and metrics
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
