Lower Bounds for Convexity Testing

We consider the problem of testing whether an unknown and arbitrary set S ⊆ R n (given as a black-box membership oracle) is convex, versus ε-far from every convex set, under the standard Gaussian distribution. The current state-of-the-art testing algorithms for this problem make 2 Õ( √ n)•poly(1/ε) 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 ε > 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 ε 1 -close to convex versus ε 2 -far from convex, for some absolute constants 0 < ε 1 < ε 2 .