Lower Bounds for Convexity Testing

Abstract

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 $\epsilon$-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/\epsilon )}$ 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^{\hat{I}\text{c◯}(1)}$ queries in order to test to some constant accuracy $\epsilon >0$. - We show that any non-adaptive tolerant tester (which may make two-sided errors) must use at least $2^{\hat{I}\text{c◯}(n^{1/4})}$ queries to distinguish sets that are ${\epsilon }_1$-close to convex versus ${\epsilon }_2$-far from convex, for some absolute constants $0<{\epsilon }_1<{\epsilon }_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 $\epsilon >0$.

52 pages, to appear in SODA 2025