Coresets are arguably the most popular compression paradigm for center-based clustering objectives such as$k$-means. Given a point set$P$, a coreset$\Omega$is a small, weighted summary that preserves the cost of all candidate solutions$S$up to a$(1\pm\varepsilon)$factor. For$k$-means in$d$-dimensional Euclidean space the cost for solution$S$is$\Sigma_{p\in P}{\min}_{s\in S}\Vert p-s\Vert ^2$. A very popular method for coreset construction, both in theory and practice, is Sensitivity Sampling, where points are sampled in proportion to their importance. We show that Sensitivity Sampling yields optimal coresets of size$\widetilde{O}(k/\varepsilon^{2}\min(\sqrt{k},\varepsilon^{-2}))$for worst-case instances. Uniquely among all known coreset algorithms, for well-clusterable data sets with$\Omega(1)$, cost stability, Sensitivity Sampling gives coresets of size$\widetilde{O}(k/\varepsilon^{2})$, improving over the worst-case lower bound. Notably, Sensitivity Sampling does not have to know the cost stability in order to exploit it: it is appropriately sensitive to the clusterability of the data set while being oblivious to it. We also show that any coreset for stable instances consisting of only input points must have size$\Omega(k/\varepsilon^{2})$. Our results for Sensitivity Sampling also extend to the k-median problem, and more general metric spaces.

In the Generalized Mastermind problem, there is an unknown subset $H$ of the hypercube 0,1$^d$ containing $n$ points. The goal is to learn $H$ by making a few queries to an oracle which given a point $q$ in 0,1$^d$, returns the point in $H$ nearest to $q$. We give a two-round adaptive algorithm for this problem that learns $H$ while making at most $\exp(\widetilde{O}(\sqrt{d \log n}))$. Furthermore, we show that any $r$-round adaptive randomized algorithm that learns $H$ with constant probability must make $\exp(\Omega(d^{3^{-(r-1)}}))$ queries even when the input has poly$(d)$ points; thus, any poly$(d)$ query algorithm must necessarily use $\Omega(\log \log d)$ rounds of adaptivity. We give optimal query complexity bounds for the variant of the problem where queries are allowed to be from 0,1,2$^d$. We also study a continuous variant of the problem in which $H$ is a subset of unit vectors in $\mathbb{R}^d$ and one can query unit vectors in $\mathbb{R}^d$. For this setting, we give a $O(n^{\lfloor d/2 \rfloor})$ query deterministic algorithm to learn the hidden set of points.