Testing Sumsets is Hard

Abstract

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 $\hat{I}\text{c◯}(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.

18 pages