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.

Authors

• Anindya De
• Shivam Nadimpalli
• Rocco A. Servedio

Keywords

No keywords are indexed for this paper.