Testing Sumsets is Hard

Xi Chen, Shivam Nadimpalli, Tim Randolph +2

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 add…