The work of [1]} considers unlearning in \(k\) -means clustering. The key algorithmic technique is randomized quantization of vectors to a \(\tau \) -lattice.
The intuition is that if the vector is an average of \(n\)  data points which are bounded in norm, then upon changing one data point, the vectors \(O{\frac{1}{n}}\)  close.
Therefore, if the lattice is sufficiently coarse, then it would ensure that both are mapped up the same point in the lattice. However, if we consider deterministic quantization, then there exists points such that for any \(\epsilon >0\) , shifting the point by \(\epsilon \)  changes the quantized point. Therefore, we first shift the lattice by a uniformly random phase, which ensures that such a situation occurs with a small probability.
