Approximating Sumset Size.
A. De and S. Nadimpalli and R. Servedio.
ACM-SIAM Symposium on Discrete Algoithms (SODA), pp. 2339-2357, 2022.


Abstract:

Given a subset $A$ of the $n$-dimensional Boolean hypercube $\F_2^n$, the \emph{sumset} $A+A$ is the set $\{a+a': a, a' \in A\}$ where addition is in $\F_2^n$. Sumsets play an important role in additive combinatorics, where they feature in many central results of the field.

The main result of this paper is a sublinear-time algorithm for the problem of \emph{sumset size estimation}. In more detail, our algorithm is given oracle access to (the indicator function of) an arbitrary $A \subseteq \F_2^n$ and an accuracy parameter $\eps$, and with high probability it outputs a value $0 \leq v \leq 1$ that is $\pm \eps$-close to $\Vol(A' + A')$ for some perturbation $A' \subseteq A$ of $A$ satisfying $\Vol(A \setminus A') \leq \eps.$ It is easy to see that without the relaxation of dealing with $A'$ rather than $A$, any algorithm for estimating $\Vol(A+A)$ to any nontrivial accuracy must make $2^{\Omega(n)}$ queries. In contrast, we give an algorithm whose query complexity depends only on $\eps$ and is completely independent of the ambient dimension $n$.

pdf of full version on arxiv


Back to main papers page