Nearest Neighbor Representations of Boolean Functions.
Péter HajnalZhihao LiuGyörgy TuránPublished in: AI&M (2006)
Keyphrases
- boolean functions
- nearest neighbor
- uniform distribution
- k nearest neighbor
- knn
- threshold functions
- high dimensional
- dnf formulae
- functional properties
- prime implicants
- training set
- membership queries
- read once formulas
- multi valued
- bi decomposition
- relevant variables
- linear threshold
- polynomial size
- search space
- dnf formulas
- statistical queries
- neural network
- automated reasoning
- desirable properties
- truth table