Report
Testing Sumsets is Hard
| العنوان: | Testing Sumsets is Hard |
|---|---|
| المؤلفون: | Chen, Xi, Nadimpalli, Shivam, Randolph, Tim, Servedio, Rocco A., Zamir, Or |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity, Mathematics - Combinatorics |
| الوصف: | A subset $S$ of the Boolean hypercube $\mathbb{F}_2^n$ is a sumset if $S = \{a + b : a, b\in A\}$ for some $A \subseteq \mathbb{F}_2^n$. Sumsets are central objects of study in additive combinatorics, featuring in several influential results. We prove a lower bound of $\Omega(2^{n/2})$ for the number of queries needed to test whether a Boolean function $f:\mathbb{F}_2^n \to \{0,1\}$ is the indicator function of a sumset. Our lower bound for testing sumsets follows from sharp bounds on the related problem of shift testing, which may be of independent interest. We also give a near-optimal $2^{n/2} \cdot \mathrm{poly}(n)$-query algorithm for a smoothed analysis formulation of the sumset refutation problem. Comment: 18 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2401.07242 |
| رقم الانضمام: | edsarx.2401.07242 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |