Can We Spot a Fake?

Abstract. The problem of detecting fake data inspires the following seemingly simple mathematical question. Sample a data point [Formula: see text] from the standard normal distribution in [Formula: see text]. An adversary observes [Formula: see text] and corrupts it by adding a vector [Formula: see text], where they can choose any vector [Formula: see text] from a fixed set [Formula: see text] of the adversary’s “tricks” and where [Formula: see text] is a fixed radius. The adversary’s choice of [Formula: see text] may depend on the true data [Formula: see text]. The adversary wants to hide the corruption by making the fake data [Formula: see text] statistically indistinguishable from the real data [Formula: see text]. What is the largest radius [Formula: see text] for which the adversary can create an undetectable fake? We show that for highly symmetric sets [Formula: see text], the detectability radius [Formula: see text] is approximately twice the scaled Gaussian width of [Formula: see text]. The upper bound actually holds for arbitrary sets [Formula: see text] and generalizes to arbitrary, non-Gaussian distributions of real data [Formula: see text]. The lower bound may fail for not highly symmetric [Formula: see text], but we conjecture that this problem can be solved by considering the focused version of the Gaussian width of [Formula: see text], which focuses on the most important directions of [Formula: see text].