Lower Bounds for Convexity Testing.
X. Chen and A. De and S. Nadimpalli and R. Servedio and E. Waingarten.
36th Symposium on Discrete Algorithms (SODA), 2025.

Abstract:

We consider the problem of testing whether an unknown and arbitrary set $S \subseteq \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^{\Omega(1)}$ queries in order to test to some constant accuracy $\varepsilon.$
  • We show that any non-adaptive \emph{tolerant} tester (which may make two-sided errors) must use at least $2^{\Omega(n^{1/4})}$ queries to distinguish sets that are $\varepsilon_1$-close to convex versus $\varepsilon_2$-far from convex, for some absolute constants $\varepsilon_1,\varepsilon_2$.

    • Finally, we also show that for any positive constant $c$, 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$.

    Back to main papers page