Robust mean estimation is the problem of estimating the mean $\mu \in
\mathbb{R}^d$ of a $d$-dimensional distribution $D$ from a list of independent
samples, an $\epsilon$-fraction of which have been arbitrarily corrupted by a
malicious adversary. Recent algorithmic progress has resulted in the first
polynomial-time algorithms which achieve \emph{dimension-independent} rates of
error: for instance, if $D$ has covariance $I$, in polynomial-time one may find
$\hat{\mu}$ with $\|\mu - \hat{\mu}\| \leq O(\sqrt{\epsilon})$. However, error
rates achieved by current polynomial-time algorithms, while
dimension-independent, are sub-optimal in many natural settings, such as when
$D$ is sub-Gaussian, or has bounded $4$-th moments.
In this work we give worst-case complexity-theoretic evidence that improving
on the error rates of current polynomial-time algorithms for robust mean
estimation may be computationally intractable in natural settings. We show that
several natural approaches to improving error rates of current polynomial-time
robust mean estimation algorithms would imply efficient algorithms for the
small-set expansion problem, refuting Raghavendra and Steurer's small-set
expansion hypothesis (so long as $P \neq NP$). We also give the first direct
reduction to the robust mean estimation problem, starting from a plausible but
nonstandard variant of the small-set expansion problem.

该论文阐述了在自然情况下改善多项式算法稳健均值估计误差率在计算上可能是不可行的，并探索了改善现有算法的错误率的自然方法，并证明了这将意味着小集合扩展问题的有效算法。