Lower Bounds for Convexity Testing
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909360601432064 |
|---|---|
| author | Chen, Xi De, Anindya Nadimpalli, Shivam Servedio, Rocco A. Waingarten, Erik |
| author_facet | Chen, Xi De, Anindya Nadimpalli, Shivam Servedio, Rocco A. Waingarten, Erik |
| contents | We consider the problem of testing whether an unknown and arbitrary set $S \subseteq \mathbb{R}^n$ (given as a black-box membership oracle) is convex, versus $\varepsilon$-far from every convex set, under the standard Gaussian distribution. The current state-of-the-art testing algorithms for this problem make $2^{\tilde{O}(\sqrt{n})\cdot \mathrm{poly}(1/\varepsilon)}$ non-adaptive queries, both for the standard testing problem and for tolerant testing.
We give the first lower bounds for convexity testing in the black-box query model:
- We show that any one-sided tester (which may be adaptive) must use at least $n^{Ω(1)}$ queries in order to test to some constant accuracy $\varepsilon>0$.
- We show that any non-adaptive tolerant tester (which may make two-sided errors) must use at least $2^{Ω(n^{1/4})}$ queries to distinguish sets that are $\varepsilon_1$-close to convex versus $\varepsilon_2$-far from convex, for some absolute constants $0<\varepsilon_1<\varepsilon_2$.
Finally, we also show that for any constant $c>0$, any non-adaptive tester (which may make two-sided errors) must use at least $n^{1/4 - c}$ queries in order to test to some constant accuracy $\varepsilon>0$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_17958 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lower Bounds for Convexity Testing Chen, Xi De, Anindya Nadimpalli, Shivam Servedio, Rocco A. Waingarten, Erik Computational Complexity Data Structures and Algorithms We consider the problem of testing whether an unknown and arbitrary set $S \subseteq \mathbb{R}^n$ (given as a black-box membership oracle) is convex, versus $\varepsilon$-far from every convex set, under the standard Gaussian distribution. The current state-of-the-art testing algorithms for this problem make $2^{\tilde{O}(\sqrt{n})\cdot \mathrm{poly}(1/\varepsilon)}$ non-adaptive queries, both for the standard testing problem and for tolerant testing. We give the first lower bounds for convexity testing in the black-box query model: - We show that any one-sided tester (which may be adaptive) must use at least $n^{Ω(1)}$ queries in order to test to some constant accuracy $\varepsilon>0$. - We show that any non-adaptive tolerant tester (which may make two-sided errors) must use at least $2^{Ω(n^{1/4})}$ queries to distinguish sets that are $\varepsilon_1$-close to convex versus $\varepsilon_2$-far from convex, for some absolute constants $0<\varepsilon_1<\varepsilon_2$. Finally, we also show that for any constant $c>0$, any non-adaptive tester (which may make two-sided errors) must use at least $n^{1/4 - c}$ queries in order to test to some constant accuracy $\varepsilon>0$. |
| title | Lower Bounds for Convexity Testing |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.17958 |