2024/10/23 by Xin Chen, Chen, Xi, Anindya De +7 · 2 citations
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2410.17958
openalex publication_date 2024/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of testing whether an unknown and arbitrary set S ⊆ ℝ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^O(√(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^Ω(n1/4) queries to distinguish sets that are ε1-close to convex versus ε2-far from convex, for some absolute constants 0<ε1<ε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 n1/4 - c queries in order to test to some constant accuracy ε>0.