Book ; Online: Testing Sumsets is Hard
2024
Abstract: ... in A\}$ for some $A \subseteq \mathbb{F}_2^n$. Sumsets are central objects of study in additive combinatorics ...
Abstract | 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^{O(n/2)} \cdot \mathrm{poly}(n)$}-query algorithm for a smoothed analysis formulation of the sumset *refutation* problem. Comment: 18 pages |
---|---|
Keywords | Computer Science - Data Structures and Algorithms ; Computer Science - Computational Complexity ; Mathematics - Combinatorics |
Publishing date | 2024-01-14 |
Publishing country | us |
Document type | Book ; Online |
Database | BASE - Bielefeld Academic Search Engine (life sciences selection) |
Full text online
More links
Kategorien
Inter-library loan at ZB MED
Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.