Cover Image

Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Deng, Chengyuan, Gao, Jie, Lu, Kevin, Luo, Feng, Xin, Cheng
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
by: Bogdanov, Andrej, et al.
Published: (2025)

Simple, unified analysis of Johnson-Lindenstrauss with applications
by: Li, Yingru
Published: (2024)

Low Sensitivity Hopsets
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

The Discrepancy of Shortest Paths
by: Bodwin, Greg, et al.
Published: (2024)

Dynamic Construction of the Lovász Local Lemma
by: Haeupler, Bernhard, et al.
Published: (2026)

Approximating Traveling Salesman Problems Using a Bridge Lemma
by: Böhm, Martin, et al.
Published: (2024)

New Graph and Hypergraph Container Lemmas with Applications in Property Testing
by: Blais, Eric, et al.
Published: (2024)

A simple algorithm for Combinatorial n-fold ILPs using the Steinitz Lemma
by: Gupta, Sushmita, et al.
Published: (2025)

Notes on the Linear Algebraic View of Regularity Lemmas
by: Bodwin, Greg, et al.
Published: (2025)

Distributed Algorithms for Euclidean Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Fully Dynamic Euclidean k-Means
by: Bhattacharya, Sayan, et al.
Published: (2025)

On the Price of Differential Privacy for Hierarchical Clustering
by: Deng, Chengyuan, et al.
Published: (2025)

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
by: Gao, Jie, et al.
Published: (2025)

Facility Location on High-dimensional Euclidean Spaces
by: Lee, Euiwoong, et al.
Published: (2025)

A new notion of commutativity for the algorithmic Lovász Local Lemma
by: Harris, David G., et al.
Published: (2020)

A Sampling Lovász Local Lemma for Large Domain Sizes
by: Wang, Chunyang, et al.
Published: (2023)

Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation
by: Lu, Shangqi, et al.
Published: (2025)

Most Juntas Saturate the Hardcore Lemma
by: Kumar, Vinayak M.
Published: (2025)

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
by: Menand, Nicolas, et al.
Published: (2025)

Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree Problem
by: Bläsius, Thomas, et al.
Published: (2025)

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
by: Goranci, Gramoz, et al.
Published: (2025)

Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights
by: Moretti, Simone, et al.
Published: (2022)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Mömke, Tobias, et al.
Published: (2024)

A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean TSP
by: Baligács, Júlia, et al.
Published: (2024)

Enabling Asymptotic Truth Learning in a Social Network
by: Lu, Kevin, et al.
Published: (2024)

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
by: Bodwin, Greg, et al.
Published: (2023)

Space Complexity of Euclidean Clustering
by: Zhu, Xiaoyi, et al.
Published: (2024)

RCM++:Reverse Cuthill-McKee ordering with Bi-Criteria Node Finder
by: Hou, JiaJun, et al.
Published: (2024)

Approximate Counting in Local Lemma Regimes
by: Mann, Ryan L., et al.
Published: (2025)

Optimally Improving Cooperative Learning in a Social Setting
by: Haddadan, Shahrzad, et al.
Published: (2024)

Adwords with Unknown Budgets and Beyond
by: Udwani, Rajan
Published: (2021)

Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search
by: Gao, Jianyang, et al.
Published: (2024)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

Going Beyond Surfaces in Diameter Approximation
by: Włodarczyk, Michał
Published: (2025)

Static Retrieval Revisited: To Optimality and Beyond
by: Hu, Yang, et al.
Published: (2025)

Correlation Clustering Beyond the Pivot Algorithm
by: Behnezhad, Soheil, et al.
Published: (2024)

Hardness and Approximation Algorithms for Balanced Districting Problems
by: Dharangutte, Prathamesh, et al.
Published: (2025)

Beyond 2-approximation for k-Center in Graphs
by: Jin, Ce, et al.
Published: (2025)

Online Metric Matching: Beyond the Worst Case
by: Yang, Mingwei, et al.
Published: (2024)