How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals

ArXi:2604.26972v1 Announce Type: cross This paper studies the computational difficulty of clustering problems that are defined directly on a continuous probability density. Rather than working with finite samples, we assume the density is given as a polynomial and ask whether it contains certain cluster structures. Four natural questions are examined. First, do there exist several points with high density that are far apart from each other. Second, do two high density points have a midpoint with low density, creating a valley between them.