  A subset $S$ of the Boolean hypercube $\mathbb{F}_2^n$ is a sumset if $S =
\{a + b : a, b\in A\}$ for some $A \subseteq \mathbb{F}_2^n$. Sumsets are
central objects of study in additive combinatorics, featuring in several
influential results. We prove a lower bound of $\Omega(2^{n/2})$ for the number
of queries needed to test whether a Boolean function $f:\mathbb{F}_2^n \to
\{0,1\}$ is the indicator function of a sumset. Our lower bound for testing
sumsets follows from sharp bounds on the related problem of shift testing,
which may be of independent interest. We also give a near-optimal $2^{n/2}
\cdot \mathrm{poly}(n)$-query algorithm for a smoothed analysis formulation of
the sumset refutation problem.
