Nearest neighbor representations of Boolean functions.
Péter HajnalZhihao LiuGyörgy TuránPublished in: CoRR (2020)
Keyphrases
- boolean functions
- nearest neighbor
- uniform distribution
- k nearest neighbor
- knn
- data points
- functional properties
- prime implicants
- relevant variables
- high dimensional
- multi valued
- membership queries
- threshold functions
- dnf formulae
- polynomial size
- training set
- pac learning
- statistical queries
- pseudo boolean functions
- dnf formulas
- agnostic learning