2021/07/26 by Anindya De, De, Anindya, Shivam Nadimpalli +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2107.12367
openalex publication_date 2021/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a subset A of the n-dimensional Boolean hypercube \mathbbF2n, the sumset A+A is the set \a+a': a, a' ∈ A\ where addition is in \mathbbF2n. 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 A ⊆ \mathbbF2n 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.