Cover Image

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gao, Jie, Jayaram, Rajesh, Kolbe, Benedikt, Sapir, Shay, Schwiegelshohn, Chris, Silwal, Sandeep, Waingarten, Erik
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
by: Beretta, Lorenzo, et al.
Published: (2025)

Data-Dependent LSH for the Earth Mover's Distance
by: Jayaram, Rajesh, et al.
Published: (2024)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
by: Silwal, Sandeep, et al.
Published: (2025)

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

Settling Time vs. Accuracy Tradeoffs for Clustering Big Data
by: Draganov, Andrew, et al.
Published: (2024)

Moderate Dimension Reduction for $k$-Center Clustering
by: Jiang, Shaofeng H. -C., et al.
Published: (2023)

Instance-Optimal Uniformity Testing and Tracking
by: Blanc, Guy, et al.
Published: (2025)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
by: Krivošija, Amer, et al.
Published: (2025)

On the Adversarial Robustness of Online Importance Sampling
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Optimal Algorithms for Augmented Testing of Discrete Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2024)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
by: Khanna, Sanjeev, et al.
Published: (2025)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
by: Charikar, Moses, et al.
Published: (2024)

How fast can you find a good hypothesis?
by: Aamand, Anders, et al.
Published: (2025)

Connectivity Labeling in Faulty Colored Graphs
by: Petruschka, Asaf, et al.
Published: (2024)

A Bi-metric Framework for Fast Similarity Search
by: Xu, Haike, et al.
Published: (2024)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

On the Structure of Replicable Hypothesis Testers
by: Aamand, Anders, et al.
Published: (2025)

Improved Approximations for Hard Graph Problems using Predictions
by: Aamand, Anders, et al.
Published: (2025)

Learning-Augmented Frequent Directions
by: Aamand, Anders, et al.
Published: (2025)

Robust Streaming Against Low-Memory Adversaries
by: Ben-Eliezer, Omri, et al.
Published: (2025)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
by: Parter, Merav, et al.
Published: (2024)

Simple and Optimal Sublinear Algorithms for Mean Estimation
by: Bertolotti, Beatrice, et al.
Published: (2024)

Nearly Tight Bounds on Testing of Metric Properties
by: Bao, Yiqiao, et al.
Published: (2024)

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

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
by: Cohen-Addad, Vincent, et al.
Published: (2022)

Streaming Algorithms with Few State Changes
by: Jayaram, Rajesh, et al.
Published: (2024)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
by: Bakshi, Ainesh, et al.
Published: (2023)

Statistical-Computational Trade-offs for Density Estimation
by: Aamand, Anders, et al.
Published: (2024)

Sparse Random Matrices for Dimensionality Reduction
by: Mackenzie, Pierre
Published: (2025)

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
by: Chakrabarty, Deeparnab, et al.
Published: (2025)

Efficiently Computing Similarities to Private Datasets
by: Backurs, Arturs, et al.
Published: (2024)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
by: Cohen-Addad, Vincent, et al.
Published: (2025)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
by: Bansal, Nikhil, et al.
Published: (2024)

Average-Distortion Sketching
by: Bao, Yiqiao, et al.
Published: (2024)

Skirting Additive Error Barriers for Private Turnstile Streams
by: Aamand, Anders, et al.
Published: (2026)

Dynamic PageRank: Algorithms and Lower Bounds
by: Jayaram, Rajesh, et al.
Published: (2024)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)