Testing Sumsets is Hard.
X. Chen and S. Nadimpalli and T. Randolph and R. Servedio and O. Zamir.
In European Symposium on Algorithms (ESA), 2025, to appear.


Abstract:

A subset $S$ of the Boolean hypercube $\F_2^n$ is a \emph{sumset} if $S = \{a + b : a, b\in A\}$ for some $A \subseteq \F_2^n$. Sumsets are central objects of study in additive combinatorics, where they play a role in several of the field's most important results. We prove a lower bound of $\Omega(2^{n/2})$ for the number of queries needed to test whether a Boolean function $f:\F_2^n \to \{0,1\}$ is the indicator function of a {sumset}, ruling out an efficient testing algorithm for sumsets.

Our lower bound for testing sumsets follows from sharp bounds on the related problem of \emph{shift testing}, which may be of independent interest. We also give a near-optimal {$2^{n/2} \cdot \poly(n)$}-query algorithm for a smoothed analysis formulation of the sumset \emph{refutation} problem. Finally, we include a simple proof that the number of different sumsets in~$\F_2^n$ is~$2^{\left(1\pm o\left(1\right)\right)2^{n-1}}$.

Link to full version


Back to main papers page