Sample-based high-dimensional convexity testing

Xi Chen, Adam Freilich, Rocco A. Servedio +1

In the problem of high-dimensional convexity testing, there is an unknown set $S\subseteq {\mathbb{R}}^n$ which is promised to be either convex or $\epsilon$-far from every conve…