The Euclidean linear-in-k inverse-square-error boundary bound
ProvedTightCoreset2027.Euclidean.baseline_coreset_lower_boundclusteringcomputational-geometrycoresets
For each fixed real , there is a constant such that, for every integer and every , a finite dataset in some positive Euclidean dimension forces every strong subset coreset with arbitrary nonnegative weights to satisfy
For errors below one half this is the subset, zero-offset specialization of CALSS22 Theorem11. The remaining error range is covered by the -point argument used in §2.3 and §2.5 of the mission source. This boundary result supplies parameter regimes in which rounding prevents use of the multi-level construction.
Preamble
import Definitions.Def_TightCoreset2027_Euclidean_generalPowers open scoped BigOperators set_option autoImplicit false
Formal statement
namespace TightCoreset2027.Euclidean
theorem baseline_coreset_lower_bound (z : ℝ) (hz : 1 ≤ z) :
∃ c : ℝ, 0 < c ∧ ∀ k : ℕ, 1 ≤ k → ∀ ε : ℝ, 0 < ε → ε < 1 →
∃ d : ℕ, 1 ≤ d ∧ ∃ X : Finset (Point d),
∀ (S : Finset (Point d)) (w : Point d → NNReal),
IsStrongCoreset z ε k X S w →
c * (k : ℝ) * Real.rpow ε (-2) ≤ (S.card : ℝ) := by sorry
end TightCoreset2027.EuclideanSource
Cohen-Addad–Larsen–Saulpic–Schwiegelshohn, Towards Optimal Lower Bounds for k-median and k-means Coresets, arXiv:2202.12793, Theorem11 (Euclidean lower bound); https://cs.au.dk/~larsen/papers/CoreSetKMeans.pdf . Used by Hu–Huang–Li–Xu, STOC2027 submission879, §2.3 printed p.16 and §2.5 printed p.20, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/879.pdf