Testing Convexity of Discrete Sets in High Dimensions
share
We study the problem of testing whether an unknown set S in n dimensions is convex or far from convex, using membership queries. The simplest high-dimensional discrete domain where the problem of testing convexity is non-trivial is the domain {-1,0,1}^n. Our main results are nearly-tight upper and lower bounds of 3^Θ( √(n)) for one-sided error testing of convex sets over this domain with non-adaptive queries. Together with our 3^Ω(n) lower bound on one-sided error testing with samples, this shows that non-adaptive queries are significantly more powerful than samples for this problem.
READ FULL TEXT