Buchumschlag

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bakshi, Ainesh, Cohen-Addad, Vincent, Hopkins, Samuel B., Jayaram, Rajesh, Lattanzi, Silvio
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Data Structures and Algorithms Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Additive Approximation Schemes for Low-Dimensional Embeddings
von: Anderson, Prashanti, et al.
Veröffentlicht: (2025)

Entrywise Low-Rank Approximation and Matrix $p \rightarrow q$ Norms via Global Correlation Rounding
von: Anderson, Prashanti, et al.
Veröffentlicht: (2026)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
von: Beretta, Lorenzo, et al.
Veröffentlicht: (2025)

Dynamic Correlation Clustering in Sublinear Update Time
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

Retriever Portfolios: A Principled Approach to Adaptive RAG
von: Stouras, Miltiadis, et al.
Veröffentlicht: (2026)

An Improved Classical Singular Value Transformation for Quantum Machine Learning
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2023)

A Scalable Algorithm for Individually Fair K-means Clustering
von: Bateni, MohammadHossein, et al.
Veröffentlicht: (2024)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

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

Rapid mixing for high-temperature Gibbs states with arbitrary external fields
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2026)

Multi-View Stochastic Block Models
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

Correlation Clustering Beyond the Pivot Algorithm
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Efficient Certificates of Anti-Concentration Beyond Gaussians
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2024)

An Improved Greedy Approximation for (Metric) $k$-Means
von: Charikar, Moses, et al.
Veröffentlicht: (2026)

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
von: Barto, Libor, et al.
Veröffentlicht: (2024)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)

A Dobrushin condition for quantum Markov chains: Rapid mixing and conditional mutual information at high temperature
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2025)

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

A Strong Linear Programming Relaxation for Weighted Tree Augmentation
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Distributed Algorithms for Euclidean Clustering
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion
von: Li, Yingxi, et al.
Veröffentlicht: (2025)

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2026)

Data-Dependent LSH for the Earth Mover's Distance
von: Jayaram, Rajesh, et al.
Veröffentlicht: (2024)

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

Scalable Private Partition Selection via Adaptive Weighting
von: Chen, Justin Y., et al.
Veröffentlicht: (2025)

Streaming Algorithms with Few State Changes
von: Jayaram, Rajesh, et al.
Veröffentlicht: (2024)

Bi-Criteria Metric Distortion
von: Banihashem, Kiarash, et al.
Veröffentlicht: (2024)

Learning quantum Hamiltonians at any temperature in polynomial time
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2023)

Structure learning of Hamiltonians from real-time evolution
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2024)

Sample-Optimal Private Regression in Polynomial Time
von: Anderson, Prashanti, et al.
Veröffentlicht: (2025)

High-Temperature Gibbs States are Unentangled and Efficiently Preparable
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2024)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
von: Axiotis, Kyriakos, et al.
Veröffentlicht: (2024)

Understanding the Cluster LP for Correlation Clustering
von: Cao, Nairen, et al.
Veröffentlicht: (2024)

Fair Clustering in the Sliding Window Model
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

Combinatorial Correlation Clustering
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
von: Diakonikolas, Ilias, et al.
Veröffentlicht: (2024)

Almost Tight Bounds for Differentially Private Densest Subgraph
von: Dinitz, Michael, et al.
Veröffentlicht: (2023)