2026-07-20T11:27:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7586 2024-03-12T11:58:25Z ddc:004 open_access

Sample-Based High-Dimensional Convexity Testing Chen, Xi Freilich, Adam Servedio, Rocco A. Sun, Timothy Property testing convexity sample-based testing In the problem of high-dimensional convexity testing, there is an unknown set S in the n-dimensional Euclidean space which is promised to be either convex or c-far from every convex body with respect to the standard multivariate normal distribution. The job of a testing algorithm is then to distinguish between these two cases while making as few inspections of the set S as possible. In this work we consider sample-based testing algorithms, in which the testing algorithm only has access to labeled samples (x,S(x)) where each x is independently drawn from the normal distribution. We give nearly matching sample complexity upper and lower bounds for both one-sided and two-sided convexity testing algorithms in this framework. For constant c, our results show that the sample complexity of one-sided convexity testing is exponential in n, while for two-sided convexity testing it is exponential in the square root of n. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xi Chen and Adam Freilich and Rocco A. Servedio and Timothy Sun 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.37 urn:nbn:de:0030-drops-75867 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.37 eng https://creativecommons.org/licenses/by/3.0/legalcode