Testing Convexity of Discrete Sets in High Dimensions

05/04/2023
by   Hadley Black, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset

Sign in with Google

×

Use your Google Account to sign in to DeepAI

×

Consider DeepAI Pro