Report
Approximating Sumset Size
| العنوان: | Approximating Sumset Size |
|---|---|
| المؤلفون: | De, Anindya, Nadimpalli, Shivam, Servedio, Rocco A. |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Computer Science - Discrete Mathematics, Mathematics - Combinatorics |
| الوصف: | Given a subset $A$ of the $n$-dimensional Boolean hypercube $\mathbb{F}_2^n$, the sumset $A+A$ is the set $\{a+a': a, a' \in A\}$ where addition is in $\mathbb{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 sumset size estimation. In more detail, our algorithm is given oracle access to (the indicator function of) an arbitrary $A \subseteq \mathbb{F}_2^n$ and an accuracy parameter $\epsilon > 0$, and with high probability it outputs a value $0 \leq v \leq 1$ that is $\pm \epsilon$-close to $\mathrm{Vol}(A' + A')$ for some perturbation $A' \subseteq A$ of $A$ satisfying $\mathrm{Vol}(A \setminus A') \leq \epsilon.$ It is easy to see that without the relaxation of dealing with $A'$ rather than $A$, any algorithm for estimating $\mathrm{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 $\epsilon$ and is completely independent of the ambient dimension $n$. Comment: 23 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2107.12367 |
| رقم الانضمام: | edsarx.2107.12367 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |