On the power of adaptivity in statistical adversaries
  We study a fundamental question concerning adversarial noise models in
statistical problems where the algorithm receives i.i.d. draws from a
distribution $\mathcal{D}$. The definitions of these adversaries specify the
type of allowable corruptions (noise model) as well as when these corruptions
can be made (adaptivity); the latter differentiates between oblivious
adversaries that can only corrupt the distribution $\mathcal{D}$ and adaptive
adversaries that can have their corruptions depend on the specific sample $S$
that is drawn from $\mathcal{D}$.
  In this work, we investigate whether oblivious adversaries are effectively
equivalent to adaptive adversaries, across all noise models studied in the
literature. Specifically, can the behavior of an algorithm $\mathcal{A}$ in the
presence of oblivious adversaries always be well-approximated by that of an
algorithm $\mathcal{A}'$ in the presence of adaptive adversaries? Our first
result shows that this is indeed the case for the broad class of statistical
query algorithms, under all reasonable noise models. We then show that in the
specific case of additive noise, this equivalence holds for all algorithms.
Finally, we map out an approach towards proving this statement in its fullest
generality, for all algorithms and under all reasonable noise models.
