Research map / Learning theory and algorithms / Clustering

Coresets for Clustering Using Noisy Comparisons and Few Distance Queries

NeurIPS 2026 · Learning theory and algorithms › Clustering · approach: Coresets and dynamic clustering

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies coreset construction for clustering in the Rank-Measure model, using noisy comparison queries to a quadruplet oracle and few exact distance queries.

Problem

Standard clustering coresets assume full access to pairwise distances, which is costly in many settings; algorithms may only have noisy comparison access.

Approach

Builds coresets under the Rank-Measure model, where the algorithm makes noisy comparison queries to a quadruplet oracle and only a limited number of distance queries, rather than assuming full distance access.

Closest papers by meaning

• Coresets for Clustering Under Stochastic Noise (NeurIPS 2025 · similarity 0.92)
• Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.89)
• Relative Error Fair Clustering in the Weak-Strong Oracle Model (ICML 2025 · similarity 0.89)
• Universal Weak Coreset (AAAI 2024 · similarity 0.88)
• Faster Approximation Algorithms for k-Center via Data Reduction (ICML 2025 · similarity 0.88)
• Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers (NeurIPS 2025 · similarity 0.88)