Approximating Sumset Size

Given a subset A of the n-dimensional Boolean hypercube , the sumset A+A is the set a + a′ : a, a′ ∊ A where addition is in . 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 sumset size estimation. In more detail, our algorithm is given oracle access to (the indicator function of) an arbitrary and an accuracy parameter ∊ > 0, and with high probability it outputs a value 0 ≤ v ≤ 1 that is ±∊-close to Vol (A′ + A′) for some perturbation A′ ⊆ A of A satisfying Vol (A A′) ≤ ∊. 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Ω(n) queries. In contrast, we give an algorithm whose query complexity depends only on ∊ and is completely independent of the ambient dimension n.