Testing convexity of figures under the uniform distribution.

Piotr Berman Meiram Murzabulatov Sofya Raskhodnikova

Published in: Random Struct. Algorithms (2019)

Keyphrases

uniform distribution
pac learning
boolean functions
uniformly distributed
relevant variables
membership queries
target concept
monotone boolean functions
dnf formulas
convex hull
remains np hard
random samples
agnostic learning
term dnf